Big-O notation, explained with growth curves

Suppose one program takes 3 seconds on a list of 10,000 items and another takes 5. Which is better? You can’t tell yet. If the first program’s running time grows in proportion to the square of the input size and the second grows in proportion to the size, the second wins comfortably once the list reaches a million items, whatever their timings at 10,000. Big-O is the vocabulary for that kind of statement.

Count steps, not seconds

Seconds depend on the processor, the language, the compiler and what else the computer is doing. So instead we pick a basic step, something that takes a bounded amount of time such as a comparison, an addition or an array access, and count how many of them the algorithm performs as a function of the input size $n$.

For loops this is mostly a matter of multiplying. A loop that runs $n$ times with a constant amount of work inside costs about $n$ steps. A loop inside a loop, both running $n$ times, costs $n \cdot n = n^2$. A loop that halves its counter each time runs only about $\log_2 n$ times, because that is how many halvings it takes to get from $n$ down to 1.

The stepper below runs five common loop shapes. Every square is one execution of the innermost line. Step through a small case, then drag $n$ up and watch how differently the totals grow.

Notice the triangle loop: its inner loop runs $1, 2, \dots, n$ times, for a total of $n(n+1)/2$. That is roughly half of the full nested loop, but it still grows like $n^2$. Doubling $n$ roughly quadruples the work in both. That shared growth rate is what Big-O captures.

The definitions

Let $f(n)$ be the number of steps an algorithm takes and $g(n)$ a simple comparison function such as $n^2$.

The “=” sign is a long-standing abuse of notation: $O(g(n))$ is really a set of functions, and $f(n) = O(g(n))$ means $f$ belongs to it. Donald Knuth’s 1976 note in SIGACT News is the reason computer scientists use Ω and Θ the way they do today.

A quicker test, when the limit exists: if $\lim_{n\to\infty} f(n)/g(n)$ is a finite positive number then $f = \Theta(g)$; if it is 0 then $f = O(g)$ but not $\Theta(g)$. Here $(3n^2 + 5n + 2)/n^2 \to 3$.

The usual growth classes

The chart puts them side by side. With a linear vertical axis the exponential and factorial curves leave the top of the chart almost at once; switch to a logarithmic axis to keep them in view. The table on the right turns step counts into time at a billion steps per second, which is generous for most real code.

At $n = 1000$, an $n \log_2 n$ algorithm needs about ten thousand steps, a quadratic one a million, and a cubic one a billion: microseconds, a millisecond and a second. An exponential algorithm needs about $10^{301}$ steps, which no computer will ever finish. That gap is why improving the growth rate matters far more than shaving constants.

Rules of thumb

• Drop constants and lower-order terms. $7n^3 + 100n^2 + 9 = \Theta(n^3)$.
• Sequential parts add; nested parts multiply. A linear pass followed by a quadratic one is $O(n + n^2) = O(n^2)$. A linear loop around a logarithmic one is $O(n \log n)$.
• The base of a logarithm doesn’t matter. $\log_a n = \log_b n / \log_b a$, a constant multiple, so we just write $O(\log n)$.
• Recursive algorithms give recurrences. Merge sort satisfies $T(n) = 2T(n/2) + n$, which solves to $\Theta(n \log n)$. The recursion tree visualiser solves recurrences of this shape and shows why.

Common misunderstandings

Big-O is not “the worst case”

Best, average and worst case are about which inputs you consider. O, Ω and Θ are about how you bound a function. They are independent: insertion sort’s best case (already sorted input) is $\Theta(n)$ and its worst case (reversed input) is $\Theta(n^2)$. You can see both in the sorting visualiser by choosing “Reversed” and then sorting the result again.

An upper bound can be loose

Technically linear search is $O(n^{2})$, since anything bounded by $n$ is also bounded by $n^2$. That statement is true but not useful. When people say “O” informally they usually mean the tightest bound they know, which is really Θ.

Constants still matter in practice

Asymptotic notation says nothing about small inputs. For short arrays, insertion sort often beats merge sort because its inner loop is so simple, which is why library sorting routines switch to insertion sort for small pieces. Use Big-O to rule out approaches that cannot scale, then measure.

Averages over a sequence of operations

Appending to a dynamic array occasionally costs $O(n)$, when the array is full and must be copied into a bigger one. If the capacity doubles each time, the total cost of $n$ appends is still $O(n)$, so each append is $O(1)$ amortised. Amortised analysis gives guarantees for sequences of operations rather than single ones.

References

1. D. E. Knuth, “Big Omicron and big Omega and big Theta”, ACM SIGACT News 8(2), 1976. doi:10.1145/1008328.1008329
2. D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules”, Communications of the ACM 28(2), 1985. doi:10.1145/2786.2793
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 3 covers asymptotic notation.
4. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Chapter 9 treats asymptotics in depth.