Big-O, Ω and Θ

Exact step counts are long and hard to compare. Big-O keeps only the part of the count that matters for large inputs: how fast it grows. This lesson gives the exact definitions, because you will need them to prove costs, not just guess them.

Keep only the part that grows fastest

Suppose a program takes 3n² + 10n + 50 steps. For n = 1,000, the 3n² part is 3,000,000, the 10n part is 10,000 and the 50 is just 50. As n grows, the n² part matters more and more, and the rest matters less and less.

The number 3 in front also matters less than it looks. It changes with the computer and the language. What does not change is the shape: double n, and n² grows four times. So we say the program takes O(n²) time, read as “order n squared”.

Big-O: an upper bound

Let f(n) be the number of steps, and g(n) a simple function such as n or n².

In words: from some size n₀ on, f is never more than a fixed multiple of g. What happens for small n does not matter. To prove a Big-O claim, you find a c and an n₀ that work. Step through the figure to try three choices.

The second choice shows something important. With c = 3, the bound never holds. That does not mean the claim is false. It only means that c was too small. You only need one pair c, n₀ that works.

Ω and Θ

Big-O says “at most”. Two related words say “at least” and “exactly”:

• Ω (big omega), a lower bound. f(n) is Ω(g(n)) if f(n) ≥ c × g(n) for all n ≥ n₀, for some c > 0.
• Θ (big theta), a tight bound. f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). It grows at exactly the rate of g, up to a constant.

3n + 5 is O(n), O(n²) and O(2ⁿ): all three are true, because Big-O is only an upper bound. But it is Θ(n) only. When people say “this is O(n)” they usually mean Θ(n). In this course we say Θ when the bound is tight and it matters.

These bounds describe a function, not a case. “The worst case is Θ(n)” and “the best case is Θ(1)” are both true of a linear search. Θ(1) means a constant number of steps, whatever n is.

Rules for working it out

Each rule below follows from the definition. Together they cover almost every program you will meet.

1. Drop constant factors. 5n is Θ(n). Take c = 5.
2. Keep only the biggest term. n² + 100n is Θ(n²), because 100n ≤ n² once n ≥ 100, so the total is at most 2n² from there on.
3. Steps one after another add. O(n) + O(n²) is O(n²).
4. Nested work multiplies. A loop of n passes that does O(log n) work in each pass is O(n log n).
5. The base of a log does not matter. log₂ n and log₁₀ n differ by a fixed factor of about 3.3, so both are Θ(log n).

Common mistakes

• Two different sizes. A loop over a list of length n inside a loop over a list of length m is O(n × m), not O(n²). Keep both letters.
• Big-O is not speed on small inputs. An O(n) method with a large constant can be slower than an O(n²) one for n = 20. Big-O only says which is smaller for large n.
• Hidden loops. One line of Python can be a loop: x in a, a.index(x), a[i:j], sum(a). Count them.