Big-O Notation
Quick reference
| O(1) — constant | O(1) |
| O(log n) — logarithmic | O(log n) |
| O(n) — linear | O(n) |
| O(n log n) — linearithmic | O(n log n) |
| O(n²) — quadratic | O(n²) |
| O(2ⁿ) — exponential | O(2ⁿ) |
| O(n!) — factorial | O(n!) |
Two programs that solve the same problem can both be "correct" and still be wildly different in practice — one finishes instantly, the other locks up your laptop once the input gets big. Big-O is the language for talking about that difference. It answers one question: as the input size N grows, how does the amount of work grow with it? Not "how many milliseconds did it take on my machine" — that depends on CPU speed, language, even what else is running. Big-O describes the shape of the growth curve, which is true on any machine, in any language, forever.
That's why we drop the machine-specific stuff and talk in terms of N. A loop that touches every element once does roughly N units of work, whether N is 10 or 10 million — we call that O(n). A loop nested inside another loop does roughly N × N units of work — O(n²). The exact constants (is it 2N operations or 5N?) get thrown away, because they don't change the shape of the curve, and the shape is what determines whether your program survives contact with a large input.
Within that, three cases matter: best case (the friendliest possible input — rarely useful to plan around), worst case (the input that makes your algorithm work hardest — what you should design for), and average case (what typically happens across realistic inputs — useful when worst case is rare and expensive to avoid, like a hash map's collision handling). When people say "this algorithm is O(n)" with no qualifier, they almost always mean worst case — that's the default you should assume too.
How to derive it
// The skill: read code, count how the "work" scales with N, name the class. // Ask one question per loop/structure: "does this range depend on N, and how?" // - a fixed number of steps, no matter how big N gets -> O(1) // - one pass over N items -> O(n) // - a loop inside a loop, each over N items -> O(n^2) // - a loop that cuts the remaining work in half each step -> O(log n) // Multiply nested/sequential costs, then keep only the fastest-growing term.
constant time — O(1)
function firstElement(arr):
return arr[0] // one lookup, no matter if arr has 10 or 10 million itemssingle loop — O(n)
function sum(arr):
total = 0
for x in arr: // runs exactly N times
total += x // constant work per iteration
return totalnested loop — O(n²)
function hasDuplicatePair(arr):
for i in range(len(arr)): // N times
for j in range(len(arr)): // N times, for EACH i
if i != j and arr[i] == arr[j]:
return true
return falsehalving loop — O(log n)
function binarySearch(sortedArr, target):
lo, hi = 0, len(sortedArr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sortedArr[mid] == target:
return mid
elif sortedArr[mid] < target:
lo = mid + 1
else:
hi = mid - 1 // each iteration THROWS AWAY half the remaining range
return -1These classes are listed in order from cheapest to most expensive growth. The gut-check column is the part worth memorizing — it's what tells you, mid-interview or mid-code-review, whether an approach is going to survive a realistic input size.
| Operation | Time | Space | Why |
|---|---|---|---|
| O(1) — constant | O(1) | — | Same cost at n = 10 or n = 1,000,000 — a hash lookup, an array index, a fixed arithmetic formula. |
| O(log n) — logarithmic | O(log n) | — | At n = 1,000,000, log₂n ≈ 20. Halving the problem each step gets you to the answer absurdly fast — binary search is the canonical example. |
| O(n) — linear | O(n) | — | One pass over the input. At n = 1,000,000, that's 1,000,000 operations — fast, and the best you can usually do if you must look at every element. |
| O(n log n) — linearithmic | O(n log n) | — | At n = 1,000,000, ≈ 20,000,000 operations — still fast. The signature of good sorting algorithms (merge sort, heap sort). |
| O(n²) — quadratic | O(n²) | — | At n = 1,000,000, that's a trillion operations — don't. Fine at n = 100, dangerous once input size isn't guaranteed small. Every-pair comparisons land here. |
| O(2ⁿ) — exponential | O(2ⁿ) | — | At n = 30 this is already over a billion; at n = 1,000,000 it's incomprehensibly large. Shows up in brute-force "try every subset" approaches. |
| O(n!) — factorial | O(n!) | — | At n = 20, larger than the number of atoms you can reasonably enumerate. "Try every ordering/permutation" territory — only tractable for tiny N. |
Constants aren't always noise
Big-O drops constants because they stop mattering as N grows large — but if N is capped at, say, 20 (a fixed-size board, a small config list), an O(n²) algorithm with tiny constants can beat an O(n log n) one with heavier per-step overhead in practice. Big-O describes the trend at scale, not "which code is faster on my actual input."
A shrinking loop is still O(n²)
A loop like "for i in range(n): for j in range(i, n)" looks smaller each pass — the inner loop runs n, then n-1, then n-2 times. But the total is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2, and that's still a quadratic expression. Dropping constants and lower-order terms, n(n+1)/2 is O(n²), not O(n) — total work, not per-iteration feel, is what Big-O measures.
Worst case vs. average case
A hash map lookup is O(1) on average — but if every key collides into the same bucket (bad hash function, adversarial input), it degrades to O(n) worst case, since you'd walk a full bucket chain. Quoting "O(1)" without the qualifier hides that risk; know which case you're claiming.
A hidden O(n) inside a loop
`for i in range(n): result += arr[:i]` looks like a single O(n) loop, but slicing/concatenating a string or list is itself O(k) in the size being built — so the real cost is 1 + 2 + ... + n ≈ O(n²), not O(n). Always ask whether the line inside your loop is actually constant time before counting the loop itself.
Sign in to mark problems done — progress syncs across devices.