AlgorithmsAlgorithmsCollege

Big-O Notation

Growth rates and worst-case analysis.

Big-O notation describes how an algorithm's running time or memory grows as the input size $n$ grows, ignoring constant factors and lower-order terms. An algorithm that takes $3n^2 + 5n + 2$ steps is $O(n^2)$ , because for large $n$ the $n^2$ term dominates everything else.

Common classes from fastest to slowest growth are $O(1)$ , $O(\log n)$ , $O(n)$ , $O(n \log n)$ , $O(n^2)$ and $O(2^n)$ . The difference is dramatic at scale: for a million items, $n^2$ is a trillion steps while $n \log_2 n$ is about twenty million.

Key terms

Big-O: f is O(g) if f is eventually bounded by a constant multiple of g.
$f(n) \le C\,g(n) \text{ for } n \ge n_0$

Key ideas

Drop constants and lower-order terms: $5n + 100$ is $O(n)$ .
Sequential steps add; nested loops multiply.
Halving the problem each step gives $O(\log n)$ .
Big-O usually describes the worst case unless stated otherwise.

Worked example

A loop over $n$ items contains a loop over all $n$ items, followed by a separate single loop over $n$ . What is the complexity?

Nested part: $n \times n = n^2$ steps.
Separate loop: $n$ steps.
Total: $n^2 + n$ .
Keep the dominant term: $O(n^2)$ .

Answer: $O(n^2)$

Common mistakes

Adding the costs of nested loops instead of multiplying.
Keeping constants, as in $O(2n)$ .
Assuming an $O(n)$ algorithm is always faster than $O(n^2)$ for small inputs.

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.About how many halvings take 1024 items down to 1?
Show answer
$10$
2.If an $O(n^2)$ algorithm takes 1 s for $n = 1000$ , about how long for $n = 3000$ ?
Show answer
$9$ s
3.Steps for $n \log_2 n$ when $n = 256$ .
Show answer
$2048$

Key terms

Key ideas

Worked example

Common mistakes

Practice questions

More in Algorithms