Big-O Notation
The industry's shorthand for growth: what O(1), O(n), and O(n²) mean, and why Big-O always talks about the worst case.
You now know how to say "the work doubles when the input doubles" — but that's a mouthful, and "the work quadruples when the input doubles" is worse. Programmers compress each growth shape into a tiny label: Big-O notation.
You write O(n) and read it "oh of n": the steps grow in proportion to n. The letter inside the parentheses is the growth shape:
- O(1) — "constant time": the same few steps no matter how big the input. Grabbing
items[0]from a list of ten or ten billion — one step. - O(n) — "linear time": steps grow with n. The
find_maxloop. - O(n²) — "quadratic time": steps grow with n × n. The wedding clinks, the nested loop.
Big-O is the shared vocabulary of the field. Code reviews say "this endpoint is O(n²), fix it". Interviewers ask "what's the complexity?" and expect an answer in exactly this notation.
What is the Big-O of this function?
def total(numbers):
result = 0
for num in numbers:
result += num
return result- AO(n)
- BO(1)
- CO(n²)
- DO(2n)
Two rules turn any step-count into proper Big-O:
Rule 1 — drop constants. 3n steps → O(n). n/2 steps → O(n). You learned why last lesson: constants shift the line, they don't bend the curve. Rule 2 — keep only the dominant term. A function that does a nested pass (n²) and then a single pass (n) does n² + n steps. When n = 1,000, that's 1,000,000 + 1,000 — the n is a rounding error. The biggest term drowns out the rest, so n² + n → O(n²).def analyze(items):
for a in items: # n² steps —
for b in items: # dominates everything
compare(a, b)
for item in items: # + n steps — vanishes
print(item)Think of it like describing a truck's weight: you say "about 10 tons", not "10 tons and a coffee cup". Big-O is deliberately approximate — that's what makes it portable across machines and languages.
An algorithm takes exactly 5n + 200 steps. What is its Big-O?
- AO(n)
- BO(5n + 200)
- CO(n²)
- DO(200)
One convention to lock in: Big-O describes the worst case unless someone says otherwise.
def find(items, target):
for item in items:
if item == target:
return True # might return on step 1!
return FalseIf target is the first item, this returns after one step. Lucky. But if it's the last item — or missing entirely — the loop does all n steps. When an interviewer asks "what's the complexity of find?", the expected answer is O(n): the guarantee, not the hope.
Why so pessimistic? Because real systems are sized for their worst day. A hospital pager network that's "usually fast" isn't a compliment. Plan for the worst case and the lucky days are a bonus. 😌
Accessing a list element by index, like items[42], takes the same time no matter how long the list is. In Big-O we write O(___).
A function checks every PAIR of items in a list to find duplicates, using a loop inside a loop. Worst-case Big-O?
- AO(n²)
- BO(n)
- CO(1)
- DO(n + n)
- Big-O notation labels an algorithm's growth shape: O(1) constant, O(n) linear, O(n²) quadratic.
- Drop constants: 5n + 200 → O(n). Big-O describes the curve's destiny, not its first points.
- Keep the dominant term: n² + n → O(n²) — the biggest term drowns the rest.
- Big-O means worst case by convention:
findmay get lucky, but its guarantee is O(n). - Interviews are conducted in this vocabulary — "what's the complexity?" expects exactly these labels.
Next lesson: the full family portrait — including the two classes that separate good code from great: O(log n) and O(n log n).