Big O in Three Minutes
Big O is a way of comparing two pieces of code mathematically, and how efficiently they run as the input grows.
Two things it measures:
- Time complexity — how long code takes to run. Not measured in seconds, but in the number of operations.
- Space complexity — the total memory it takes to run.
Seconds depend on your laptop. Operations don't, which is why we count those.
Why it's always the worst case
Three Greek letters show up here. Say we're searching [1, 2, 3, 4, 5, 6, 7]:
| Looking for | Case | Letter |
|---|---|---|
1 — found immediately | best | Omega Ω |
4 — somewhere in the middle | average | Theta θ |
7 — the whole list first | worst | Omicron O |
Omicron is the one we write as Big O. We plan for the worst case because that's the guarantee, best case is luck.
The four that matter
O(1) — constant
Work stays flat. Doubling the input changes nothing.
def get_first(arr):
return arr[0] # 1 operation, whether arr has 5 or 5 million itemsNo loop, no scanning. Direct access.
O(log n) — logarithmic
Each step cuts the problem in half instead of stepping through one at a time.
def count_halvings(n):
count = 0
while n > 1:
n = n // 2 # this line is the whole reason it's log n
count += 1
return countn = 16 runs 4 times, not 16. And it barely grows:
| n | iterations |
|---|---|
| 16 | 4 |
| 1,024 | 10 |
| 1,000,000 | ~20 |
A million items in about 20 steps. Change n = n // 2 to n = n - 1 and
you're straight back to O(n).
O(n) — linear
Work grows in direct proportion to input. Double the input, double the work.
def print_items(n):
for i in range(n):
print(i)10 items, 10 operations. 10,000 items, 10,000 operations. A straight line.
O(n²) — quadratic
Work grows with the square of the input. Double it, roughly quadruple the work.
for i in range(n):
for j in range(n):
print(i, j) # n × n| n | n² |
|---|---|
| 10 | 100 |
| 100 | 10,000 |
| 1,000 | 1,000,000 |
With O(n) the work adds up. With O(n²) it multiplies, so it explodes.
Two rules that simplify everything
Drop the constants. Two sequential loops over n is 2n steps, but we
still call it O(n):
for i in range(n): # n
print(i)
for j in range(n): # n
print(j)
# 2n -> O(n)Big O only cares about the shape of growth, not the exact step count. 2n
and n both grow in a straight line. The 2 never turns linear into
quadratic, so it doesn't change the answer. 2n, 5n, 100n are all O(n).
Drop the non-dominant terms. Keep only the fastest-growing part:
for i in range(n): # O(n²)
for j in range(n):
print(i, j)
for k in range(n): # O(n)
print(k)
# O(n² + n) -> O(n²)Once n is large, the O(n) part is a rounding error next to O(n²).
Different inputs get different letters
If a function takes two independent inputs, you can't collapse them into one n:
def print_items(a, b):
for i in range(a):
print(i)
for j in range(b):
print(j)
# O(a + b), not O(n)
def print_pairs(a, b):
for i in range(a):
for j in range(b):
print(i, j)
# O(a * b)Python lists, the ones that bite
| Operation | Complexity | Why |
|---|---|---|
arr[i] | O(1) | Direct memory offset |
len(arr) | O(1) | Length is stored, not counted |
arr.append(x) | O(1)* | Amortized, occasional resize averages out |
arr.pop() | O(1) | Removes the last slot, no shifting |
arr.pop(i) | O(n) | Everything after i shifts left |
arr.insert(i, x) | O(n) | Everything after i shifts right |
x in arr | O(n) | Scans until it finds a match |
arr.sort() | O(n log n) | Timsort |
The pattern: touching the end of a list is cheap, touching the middle means shifting everything after it.
All four on one chart
Same axes, same scale:
That picture is the reason we bother: at small inputs the difference is academic, and past a certain size it decides whether your code finishes at all.
These are the condensed notes. The full version, with the reasoning worked out step by step and runnable examples, lives in my DSA repo: