Big O Notation Explained: Simple Rules and Worked Examples

The formal definition

f(n) = O(g(n)) means there are constants c > 0 and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀.

Example: show 3n² + 5n + 2 = O(n²). For n ≥ 1 we have 5n ≤ 5n² and 2 ≤ 2n², so 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n². Choosing c = 10 and n₀ = 1 satisfies the definition. (n₀ = 0 would not work, because at n = 0 the left side is 2 and the right side is 0. That is why n₀ matters.)

Five simple rules

1. Drop constants: 5n and n are both O(n).
2. Keep the fastest-growing term: n² + 100n + 7 is O(n²).
3. Add for steps done one after another: an O(n) loop followed by an O(n²) loop is O(n²).
4. Multiply for nested steps: an O(n) loop inside an O(n) loop is O(n²).
5. Halving the problem each step gives log n: repeatedly dividing by 2 takes about log₂ n steps.

How fast do they grow?

Going from n = 100 to n = 1,000 makes log n barely change, multiplies n² by 100, and makes 2ⁿ unusable. That is why the class of an algorithm matters more than the speed of the computer.

Reading complexity from code

• Single loop over n items: O(n).
• Checking every pair with the inner loop starting after the outer one: n(n − 1) ÷ 2 pairs. For n = 1,000 that is 499,500 pairs, which is O(n²).
• Binary search halves the range each time. For 1,000,000 sorted items it needs at most ⌈log₂(1,000,001)⌉ = 20 comparisons, so O(log n).
• Merge sort splits in half (log n levels) and does O(n) work per level, so O(n log n).

Big O, Big Omega and Big Theta

O gives an upper bound, Ω (Omega) a lower bound, and Θ (Theta) a tight bound that is both. Saying binary search is O(n²) is technically true but useless. When people say 'Big O' informally they usually mean the tightest bound they can prove.

Common mistakes

• Thinking O(n) means exactly n steps. It means 'at most a constant times n, eventually'.
• Assuming two nested loops are always O(n²). If the inner loop runs a fixed 10 times, the total is O(n).
• Dropping a term that is not smaller, such as writing n + m as O(n) when m can be larger than n.
• Comparing algorithms only at tiny inputs, where constants dominate.

Frequently asked questions

What is the Big O of an empty loop that runs n times?

O(n): the loop control still runs n times.

Is O(2n) different from O(n)?

No. Constant factors are dropped, so both are O(n).

Does Big O describe worst case only?

No. It is an upper bound on a function, which can be the worst case, average case or any other cost function. State which case you mean.