Two programs can give the same correct answer, yet one finishes in a blink while the other runs for hours. Big-O notation is the mathematical language computer scientists use to describe how an algorithm's running time or memory grows as its input grows. It ignores machine speed and small details, and focuses on the one thing that really matters for large inputs: the rate of growth.
Why Not Just Time the Program?
Timing a program in seconds depends on the processor, the programming language, the compiler and even what else the computer is doing. Instead, we count the number of basic steps (comparisons, additions, assignments) as a function of the input size \(n\). If one algorithm takes \(3n^2 + 5n + 2\) steps and another takes \(40n\) steps, which is better? For \(n = 5\), the first takes 102 steps and the second 200. For \(n = 1000\), the first takes 3,005,002 steps and the second only 40,000. As \(n\) grows, the \(n^2\) term dominates everything else, and that is what Big-O captures.
The Formal Definition
We say \(f(n) = O(g(n))\) if there exist positive constants \(c\) and \(n_0\) such that
$$ 0 \leq f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0 $$
In words: beyond some starting point \(n_0\), \(f\) never grows faster than a constant multiple of \(g\). Big-O is an upper bound. Two companion notations complete the picture:
- Big-Omega, \(f(n) = \Omega(g(n))\): a lower bound, \(f(n) \geq c \cdot g(n)\) for large \(n\).
- Big-Theta, \(f(n) = \Theta(g(n))\): both at once, meaning \(f\) and \(g\) grow at the same rate.
In everyday speech programmers often say "Big-O" when they really mean the tight Theta bound.
Worked Example 1: Proving a Big-O Bound
Show that \(f(n) = 3n^2 + 5n + 2\) is \(O(n^2)\).
Step 1: We need constants \(c\) and \(n_0\). For \(n \geq 1\) we know \(n \leq n^2\) and \(1 \leq n^2\).
Step 2: Replace each lower-order term by an \(n^2\) term, which can only make it larger.
$$ 3n^2 + 5n + 2 \leq 3n^2 + 5n^2 + 2n^2 = 10n^2 \quad \text{for } n \geq 1 $$
Step 3: So the definition holds with \(c = 10\) and \(n_0 = 1\). Therefore \(f(n) = O(n^2)\).
Check: at \(n = 1\), \(f(1) = 10\) and \(10 \cdot 1^2 = 10\), so the inequality holds with equality. At \(n = 10\), \(f(10) = 352 \leq 1000\). Since \(f(n) \geq 3n^2\) as well, \(f(n)\) is in fact \(\Theta(n^2)\).
The general lesson: drop constant factors and keep only the highest-order term. So \(7n^3 + 100n^2\) is \(O(n^3)\), and \(5 \log n + 20\) is \(O(\log n)\).
The Common Growth Rates
From slowest-growing (best) to fastest-growing (worst):
- \(O(1)\), constant: reading an array element by index.
- \(O(\log n)\), logarithmic: binary search.
- \(O(n)\), linear: finding the largest element in an unsorted list.
- \(O(n \log n)\): merge sort, heap sort.
- \(O(n^2)\), quadratic: bubble sort, comparing every pair.
- \(O(2^n)\), exponential: checking every subset of a set.
- \(O(n!)\), factorial: trying every ordering, as in brute-force travelling salesman.
To feel the difference, here are approximate step counts for \(n = 1000\) (logarithms base 2):
| Growth rate | Steps for n = 1000 | Practical verdict |
|---|---|---|
| \(\log n\) | about 10 | instant |
| \(n\) | 1,000 | instant |
| \(n \log n\) | about 10,000 | instant |
| \(n^2\) | 1,000,000 | fast |
| \(n^3\) | 1,000,000,000 | seconds |
| \(2^n\) | about \(10^{301}\) | never finishes |
A computer doing a billion steps per second would need far longer than the age of the universe to complete \(2^{1000}\) steps. No hardware upgrade can rescue an exponential algorithm on large inputs; only a better algorithm can.
Worked Example 2: Counting Steps in Nested Loops
Consider this code, which compares each element with every element before it:
for i = 1 to n:
for j = 1 to i:
compare(a[i], a[j])
Step 1: For each value of \(i\), the inner loop runs \(i\) times.
Step 2: Total comparisons are \(1 + 2 + 3 + \dots + n\). Using the formula for the sum of the first \(n\) natural numbers:
$$ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2} $$
Step 3: Drop the constant factor \(\tfrac{1}{2}\) and the lower-order term. The running time is \(O(n^2)\).
Check: for \(n = 4\), the inner loop runs \(1 + 2 + 3 + 4 = 10\) times, and \(\frac{4 \times 5}{2} = 10\). Even though the inner loop does not always run \(n\) times, the total still grows quadratically.
Worked Example 3: Why Binary Search Is O(log n)
Binary search finds a value in a sorted list by checking the middle element and discarding half of the list each time.
Step 1: After \(k\) comparisons, the portion still being searched has size about \(\frac{n}{2^k}\).
Step 2: The search ends when one element remains:
$$ \frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n $$
Step 3: For a list of one million names, \(\log_2 1{,}000{,}000 \approx 19.93\), so at most 20 comparisons are needed. A linear search could need up to 1,000,000.
Sanity check: \(2^{20} = 1{,}048{,}576\), which is just above one million, so 20 halvings are enough.
Rules of Thumb for Analysing Code
- Sequential steps add: \(O(n) + O(n^2) = O(n^2)\); the larger term wins.
- Nested loops multiply: a loop of \(n\) inside a loop of \(n\) gives \(O(n^2)\).
- Halving the problem each step gives a \(\log n\) factor.
- Worst, best and average cases can differ. Quicksort is \(O(n \log n)\) on average but \(O(n^2)\) in its worst case.
- Space complexity uses the same notation for memory: merge sort needs \(O(n)\) extra memory, while heap sort needs only \(O(1)\).
Did You Know?
- The "O" comes from the German word Ordnung (order). The notation was introduced by Paul Bachmann in 1894 and popularised by Edmund Landau; Donald Knuth championed its use in computer science in the 1970s.
- Because \(\log_a n = \frac{\log_b n}{\log_b a}\), all logarithm bases differ only by a constant factor, so we simply write \(O(\log n)\).
- Some important algorithms run in \(O(n \log \log n)\) time, such as the Sieve of Eratosthenes for finding primes.
Key Takeaways
- Big-O describes how running time grows with input size, ignoring constants and lower-order terms.
- Formally, \(f(n) = O(g(n))\) means \(f(n) \leq c \cdot g(n)\) for all \(n \geq n_0\).
- Count loop iterations carefully; summation formulas turn code into a growth rate.
- Logarithmic and linearithmic algorithms scale beautifully, while exponential ones become hopeless quickly.
- A better algorithm beats faster hardware for large inputs.
Need help analysing an algorithm or proving a complexity bound for your assignment? Amathify's experts and PhD scholars offer step-by-step solutions through WhatsApp and the Ask a Question form.
Stuck on a problem or assignment?
Our experts and PhD scholars solve maths, physics and chemistry — step by step.