AlgoScope

Big Omega

A lower bound. The cost is at least a constant times the reference for large n.

Complexity analysis, analysis, intermediate
n 1: f 8, upper bound fails.12345678f(n)n4n814
n 1: f 8, upper bound fails.12345678f(n)n4n814

Complexity in Numbers: 3n + 5 is Theta(n)

Decision, step 2 of 10

n = 1: f = 8, between n = 1 and 4n = 4? The lower bound holds, 8 >= 1. The upper bound fails, 8 > 4: the constant 5 still dominates. Big O only promises the bound for large n.

How complexity in numbers works

Cost

Space
O(1)

Before this

Taught by the same lesson

Complexity in Numbers covers these too, in the same run.