What Big-O measures
Timing code with a stopwatch tells you how fast it is on your machine, with today's data. It does not tell you what happens when the data is ten times bigger.
Big-O notation answers that question. It describes how the amount of work grows as the input grows. The input size is called n.
- O(n): double the input, double the work.
- O(n²): double the input, four times the work.
- O(log n): double the input, one more step.
- O(1): the work does not depend on the input size at all.
It deliberately ignores details. Whether a step takes 2 nanoseconds or 20 does not matter to Big-O. Only the shape of the growth does.
Count the steps
To find the Big-O of a piece of code, count how many times its innermost line runs, in terms of n.
for i in range(n): # runs n times
total += items[i]One loop over n items: n steps. O(n).
for i in range(n):
for j in range(n): # runs n times for each i
compare(i, j)A loop inside a loop: n times n. O(n²).
So is the rule "two nested loops means O(n²)"?
Two nested loops that are not O(n²)
for i in range(n):
j = 1
while j < n:
work(i, j)
j = j * 2 # j doubles: 1, 2, 4, 8, ...It has two nested loops. But look at how the inner one moves: j doubles each time. Starting from 1, how many doublings does it take to reach n?
Example
Counting the inner loop
For n = 8, j takes the values 1, 2, 4. Three steps.
For n = 16, j takes 1, 2, 4, 8. Four steps.
For n = 1,000,000, about 20 steps.
Doubling n adds one step. That is log₂ n.
The outer loop runs n times and the inner loop runs log n times for each, so the total is O(n log n): far closer to O(n) than to O(n²).
Here are the three shapes side by side. Run it for n = 8, then switch to 16 and 32 and watch what each bar does when n doubles.
Start. n = 8. All three run an outer loop 8 times. They differ in what happens inside it.
- O(n)
- 0
- O(n log n)
- 0
- O(n²)
- 0
Count what the loop does, not how many loops there are. The words to watch for are how the loop variable changes: adding a constant gives n steps, multiplying or dividing gives log n steps.
The common shapes
| Name | Big-O | When n doubles | Typical example |
|---|---|---|---|
| Constant | O(1) | No change | Read an array item by position, look up a key in a hash map |
| Logarithmic | O(log n) | One more step | Binary search |
| Linear | O(n) | Doubles | Scan a list once |
| Linearithmic | O(n log n) | A bit more than doubles | Good sorting algorithms |
| Quadratic | O(n²) | Four times | Compare every pair |
| Exponential | O(2ⁿ) | Squares | Try every subset |
To feel the difference, here is the work for one million items:
| Big-O | Steps for n = 1,000,000 |
|---|---|
| O(log n) | 20 |
| O(n) | 1,000,000 |
| O(n log n) | 20,000,000 |
| O(n²) | 1,000,000,000,000 |
At a billion simple steps per second, the first three finish in a blink. The last takes about 17 minutes.
Three rules for simplifying
Drop constants
A loop that does 3 things per item is 3n steps. That is still O(n). Growth is what matters.
Keep only the fastest-growing part
n² + n is O(n²). For large n the n² part is nearly all of it.
One after another: add. One inside another: multiply
Two separate loops over n are O(n + n), which is O(n). One loop inside the other is O(n × n).
Key takeaways
- Big-O describes how the work grows as the input grows, not how long the code takes.
- Find it by counting how often the innermost line runs, in terms of n.
- Nested loops are not automatically O(n²): a loop whose variable doubles runs only log n times.
- Drop constants and smaller terms. Add for code in sequence, multiply for code that is nested.
- Watch for single lines that hide a loop.