Make sense of Big O
Learn to tell a single pass from a nested loop—and explain how their work grows.
Count the work, not the seconds
Imagine checking every name on a class list. With 10 names, you check 10 entries. With 100 names, you check 100. The amount of work grows with the list: this is linear growth.
Big O describes an upper bound on how an algorithm's work grows as its input grows. It does not tell you how many seconds your laptop will take.
One pass: O(n)
for name in names:
print(name)For a list of n names, the loop runs n times. Assuming each print takes a fixed amount of work, doubling the number of names doubles the work. We describe this as O(n).
Every pair: O(n²)
for first in names:
for second in names:
compare(first, second)For each of n names, the inner loop runs n times. That means n × n comparisons, assuming a comparison takes fixed work. Double n and you get four times as many comparisons.
| Names | One pass | Every pair |
|---|---|---|
| 10 | 10 | 100 |
| 20 | 20 | 400 |
| 100 | 100 | 10,000 |
Two loops do not always mean n²
Two separate passes take n + n = 2n operations. Their growth is still linear, O(n). Two nested loops may be quadratic, but you need to check how often each one actually runs.
A tighter description for our single-pass example is Θ(n). Big O is an upper bound; when comparing these examples, we use their usual tight growth classes.