Big-O & Complexity
How cost grows with input — the vocabulary every technical interview assumes you have.
40 minDifficulty 2/5cs · interviewHand-writtenWritten by a person and not yet reviewed by a second one. Checked automatically: schema, the pedagogical rules the hand-written material is held to, and every diagram parsed for real.
Why this exists
Everyone can recite that sorting is `O(n log n)`. Far fewer can say what the n is, why a hash lookup counts as `O(1)` when it obviously does work, or why their `O(n²)` code is faster than the clever `O(n log n)` version on real input. Big-O is not a measure of speed — it is a claim about how cost *grows*. Reading it as speed is why people optimise the wrong loop and leave the database round trip inside it.
The mental model
Cooking for a dinner party. Chopping one onion per guest is linear — double the guests, double the chopping. Introducing every guest to every other guest is quadratic; ten guests is manageable, a hundred is your whole evening. And finding a guest's name on the seating chart takes the same glance whether there are ten names or ten thousand. What you care about is not how long any single step takes — it is what happens when the guest list doubles.
How it works
It describes growth, and deliberately throws away everything else
Big-O drops constant factors and lower-order terms on purpose. A function that does `3n + 500` operations is `O(n)`, identical in notation to one doing `n` operations. That is not sloppiness — those constants depend on the machine, the language, the cache, and the compiler, so a notation that kept them would describe one laptop rather than an algorithm. The trade is real though: two `O(n)` algorithms can differ by a factor of fifty in practice, and Big-O will tell you nothing about which. It answers exactly one question — what happens when the input doubles — and you have to measure to answer any other.
The classes, and the code shape that produces each
You can usually read the complexity off the structure. Indexing an array or hitting a hash map is constant — the work does not depend on n at all. Halving the search space each step is logarithmic: binary search, balanced tree lookup. One pass over the input is linear. Sorting, and most divide-and-conquer, is n log n — you do log n levels of work, each costing n. A loop nested inside a loop over the same collection is quadratic. And generating every subset or permutation is exponential or factorial, which is the point at which the algorithm is the problem. The useful instinct is not memorising the list; it is asking how many times the input gets touched, and whether that count depends on the input's size.
Average, worst, and amortised are three different claims
Hash map lookup is `O(1)` on average and `O(n)` in the worst case, when every key collides. Appending to a dynamic array is `O(1)` amortised — most pushes are constant, but occasionally the array doubles and copies everything, and spreading that cost across all the pushes gives constant time per push. Quicksort is `O(n log n)` average and `O(n²)` worst. These distinctions are exactly what an interviewer is listening for, and they matter in production too: an adversary who can choose your hash keys can force the worst case deliberately, which is a real denial-of-service technique and the reason modern runtimes randomise hash seeds.
Space complexity is the half everyone forgets
The same notation applies to memory, and the elegant solution is often the expensive one. A recursive traversal costs stack proportional to the depth, so a recursive walk of a linked list is `O(n)` space where a loop is `O(1)`. Building a lookup table to turn a quadratic scan into a linear one trades `O(1)` space for `O(n)` — usually worth it, and worth *saying* rather than doing silently. In an interview, stating both complexities unprompted is one of the cheapest signals of competence available; in production it is the difference between a service that handles a large request and one that runs out of memory.
In real systems, n is small and the constant is a network call
Big-O tells you when scale will eventually kill you. It rarely tells you what is slow today. A quadratic loop over twenty items runs in microseconds; the linear loop next to it that issues one database query per iteration takes two seconds. That N+1 query pattern is `O(n)` by the notation and catastrophic in practice, because the constant factor is a network round trip rather than a comparison. So use Big-O to reject designs that cannot possibly scale, and use a profiler to find out what is actually slow — they are different tools answering different questions, and reaching for the wrong one is how people spend a day optimising code that was never the bottleneck.
The mechanism
What the classes mean at real input sizes, assuming one operation per microsecond: | n | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | |---|---|---|---|---|---| | 10 | 3µs | 10µs | 33µs | 100µs | 1ms | | 1,000 | 10µs | 1ms | 10ms | 1s | heat death | | 1,000,000 | 20µs | 1s | 20s | 11.6 days | — | Two things fall out of this table. First, the difference between `O(n)` and `O(n log n)` is almost never worth agonising over — a factor of twenty at a million elements. Second, the gap between `O(n log n)` and `O(n²)` is the difference between a page load and a support ticket. That is where the effort belongs.
flowchart TD
Q{How many times<br/>is the input touched?} -->|Not at all| C1[O of 1<br/>index, hash lookup]
Q -->|Halving each step| CL[O of log n<br/>binary search]
Q -->|Once per element| CN[O of n<br/>single pass]
Q -->|log n passes| CNL[O of n log n<br/>sorting, merge]
Q -->|Once per pair| CN2[O of n squared<br/>nested loop]
Q -->|Once per subset| CE[O of 2 to the n<br/>brute force]
CN2 --> FIX[Usually fixable:<br/>add a hash set]
CE --> FIX2[Usually needs a<br/>different algorithm]What people get wrong
- O(1) means fast.
- It means constant — independent of input size. A constant-time operation can be slow. Reading a value from disk is O(1) and roughly a hundred thousand times slower than reading it from L1 cache, which is also O(1). The notation describes the shape of the growth curve, not its height.
- An O(n log n) algorithm always beats an O(n²) one.
- Only past a crossover point that depends on the constants, and for small n the simpler algorithm usually wins. This is why real sort implementations switch to insertion sort below roughly sixteen elements — the constant factors of quicksort's partitioning dominate at that size.
- Dropping constants means constants do not matter.
- It means they are outside what the notation describes. In production they frequently dominate. An O(n) loop with a database call inside it has a constant factor measured in milliseconds. It will lose to an O(n²) loop over in-memory data at any realistic n.
- Hash map lookup is O(1), full stop.
- O(1) average, O(n) worst case when keys collide. It matters when an attacker controls the keys. Deliberately colliding hash keys is a documented denial-of-service technique, which is why runtimes now randomise their hash seeds per process.
- Big-O measures how long code takes to run.
- It bounds how the cost grows as the input grows. It says nothing about absolute time. Two functions can both be O(n) and differ by orders of magnitude. Big-O rejects designs that cannot scale; profiling finds what is actually slow. Using one for the other's job wastes days.
When not to use it
- n is bounded and small — a config list, a set of form fields, a menu.
- Whatever is clearest to read. Optimising a loop over twelve elements is a pure cost with no benefit.
- The work is dominated by input and output — network, disk, database.
- Count round trips, not operations. One query returning a thousand rows beats a thousand queries returning one, even though both are O(n).
- You need to know why the current system is slow.
- A profiler and real traffic. Big-O predicts future cliffs; it does not locate present bottlenecks.
Terms
- Asymptotic
- — Concerning behaviour as the input grows without bound. It is why constants and small terms are dropped.
- Amortised
- — Average cost per operation across a long sequence, where occasional expensive operations are spread over the cheap ones.
- Worst case
- — The most work the algorithm can do for any input of size n. The guarantee you can actually rely on.
- Big-Omega
- — A lower bound on growth, where Big-O is an upper bound. Rarely used in practice outside academic writing.
- Big-Theta
- — A tight bound — the growth is both at most and at least this. Usually what people mean when they say Big-O.
- Space complexity
- — The same growth analysis applied to memory used, including recursion stack depth.
- Crossover point
- — The input size above which an asymptotically better algorithm actually becomes faster in practice.
In an interview
What is the time and space complexity of your solution?
- states both time AND space without being asked twice
- identifies what n refers to when there are several inputs
- distinguishes average from worst case where they differ
- counts recursion stack depth as space
- names the specific operation driving the dominant term
Why is a hash map lookup considered O(1) when it has to compute a hash and handle collisions?
- hashing cost depends on the key size, not on the number of entries n
- collisions are amortised away by keeping the load factor bounded, which is why the table resizes
- worst case is O(n) when every key lands in one bucket
- adversarial key selection can force that worst case, which is why hash seeds are randomised
Can you recall it?
Explain what Big-O actually measures, and give one concrete case where a lower Big-O is the wrong choice.