Big-O intuition
Big-O describes how an algorithm's work grows with input size. Learn to recognise O(1), O(n), and O(n²) by sight — no maths required.
- Describe what Big-O notation means intuitively
- Recognise O(1), O(n), and O(n²) patterns by sight
- Explain why O(n²) becomes a problem at scale
When someone says an algorithm is "fast" or "slow," they usually mean one of two different things: fast on today's input, or fast as the input gets larger. Big-O notation is about the second question — how does the work grow as the input grows? — and that is almost always the more important one.
Big-O is not about milliseconds. It's a description of the shape of an algorithm's growth rate. Two algorithms can both run in 10 ms on a list of 100 items and behave completely differently on a list of 1 000 000.
O(1) — constant
O(1) means the work does not grow with the input size. Regardless of whether the dict has 10 entries or 10 million, a lookup takes the same number of steps.
Examples:
- Dict/set lookup:
d["alice"] - List access by index:
lst[0] - Checking a variable's value
The 1 in O(1) does not mean "one operation" — it means "a fixed, bounded
number of operations that doesn't depend on n."
O(n) — linear
O(n) means the work grows proportionally to the input size. Double the input, roughly double the work.
Examples:
- Scanning a list:
for x in lst - Counting occurrences in a list
- Building a dict from a list (one pass)
This is the baseline for most list problems. If you look at every element once, you are O(n).
O(n²) — quadratic
O(n²) means a loop inside a loop, where each loop runs over the input. At n=100 that is roughly 10 000 operations. At n=1 000 it is 1 000 000. At n=10 000 it is 100 000 000 — already slow enough to notice.
Examples:
- Checking every pair in a list: for each element, scan the rest
- Bubble sort
- The naive two-sum (before you add the dict)
The practical rule: if you write a loop inside a loop and both iterate over the same input, you have O(n²) and you should ask whether a dict or sort can remove the inner loop.
How the classes compare at scale
| n | O(1) | O(n) | O(n²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 1 000 | 1 | 1 000 | 1 000 000 |
| 10 000 | 1 | 10 000 | 100 000 000 |
| 100 000 | 1 | 100 000 | 10 000 000 000 |
At n=10 the differences are invisible. At n=100 000, O(n²) is ten billion operations — likely seconds or minutes of wall time on real hardware where O(n) finishes in a blink.
There are other classes — O(log n), O(n log n), O(2ⁿ) — but O(1), O(n), and O(n²) cover the vast majority of everyday code. Add O(log n) once you have seen binary search, and O(n log n) once you care about sorting.
Spotting complexity in code
You don't need to do maths. Ask one question: for each line, does this step run once per element, once total, or once per pair?
# O(1): one step regardless of list length
x = lst[0]
# O(n): one step per element
for x in lst:
print(x)
# O(n^2): for each element, one step per remaining element
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
print(lst[i], lst[j])That's it. Count the levels of nesting over the same input.
Where to go next
Next: measuring speed — timing O(n) and O(n²) implementations side by side so you can see the growth rate in real numbers.