Pass the coding test
Big-O Cheat Sheet: Costs, Traps And The Doubling Test
Aarav's first campus coding test. His solution is correct — he checked it by hand. It passes 8 of 12 cases. The other four say Time Limit Exceeded . His logic was fine. His loop was O(n 2 ) and n was 200,000. The judge gave up after two seconds.
12 min readFree, no email neededUpdated 11 September 2026
Big-O is a doubling test
Aarav's first campus coding test. His solution is correct — he checked it by hand. It passes 8 of 12 cases. The other four say Time Limit Exceeded. His logic was fine. His loop was O(n2) and n was 200,000. The judge gave up after two seconds.
Big-O does not tell you how many seconds your code takes. That depends on the laptop and the language. Big-O answers one question only:
When the input doubles, what happens to the work?
- Work stays exactly the same O(1)
- Work goes up by one step O(log n)
- Work doubles O(n)
- Work doubles, plus a little more O(n log n)
- Work becomes four times as much O(n2)
- Work squares itself O(2n)
Three rules and you never need maths. Drop constants: O(2n) is O(n). Drop the smaller terms: O(n2 + n) is O(n2). Assume the worst case unless the question says otherwise.
The six curves, in real time
Steps taken, for three input sizes. The last column turns steps into time.
Times are steps divided by 35 million steps a second, measured on a normal laptop: a plain 1,000,000-step Python loop took 29 ms, and a full O(n2) double loop at n = 1,000 took 24 ms. Java and C++ run roughly three to ten times faster. It does not save you.
Read the O(2n) row again. At n = 1,000 it needs a 302-digit number of steps — about 10275 times the age of the universe. That is why "just try every combination" is never the final answer.
The order, left to right, best to worst. O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n), O(n!). Anything to the right of O(n log n) needs a very small n to survive.
What the constraint is telling you
Every coding-test question prints a line like 1 <= n <= 100000. That line is the answer key. It tells you which complexity will pass before you write anything.
The safe budget. Assume the judge allows about 10 million steps per second in Python and about 100 million in Java or C++. Multiply your complexity out at the largest n in the constraint. If the answer is bigger than the budget, do not start typing — think again.
In campus drives this is worth more marks than any clever trick. Service-based companies mostly check that your loop finishes. Product-based companies ask you to say the complexity out loud before you code.
Costs, part 1 · lists and lines
Costs, part 2 · keys and order
Sorting costs
Which sort does your language use?
- Python sorted() and list.sort() use TimsortStable, O(n log n), O(n) extra space, and O(n) when the data is already almost sorted. Measured: 1,000,000 random integers took 184 ms; the same list, already sorted, took 24 ms.
- Java Collections.sort and Arrays.sort(Integer[]) use TimsortStable. Objects that compare equal keep their original order.
- Java Arrays.sort(int[]) uses dual-pivot quicksortNot stable. Modern JDKs switch to heap sort when the recursion goes too deep, so the O(n2) worst case does not bite you.
The line that wins marks: "I sort first, which is O(n log n), then one pass, which is O(n). The sort dominates, so the whole thing is O(n log n)."
Reading a loop in ten seconds
Count how many times the innermost line runs. That count, with the constants dropped, is your answer. Every number below was counted by running the code.
When you cannot see it, count it. Put a counter on the innermost line and print it for n = 4, 8 and 16. If the counter goes 4, 8, 16 you are O(n). If it goes 16, 64, 256 you are O(n2). If it goes 8, 24, 64 you are O(n log n). This takes thirty seconds and it is never wrong.
Reading a loop, continued
The only two rules. Nested loops multiply. Loops side by side add. And a loop whose length never changes with n — for c in range(26) — is a constant: 26n is still O(n).
Say it out loud while you read: "n times... n times... so n squared."
Space, and the stack trap
Space complexity is the extra memory you use — on top of the input you were handed, and usually not counting the answer you must return.
- Two pointers, a few counters, a running sum O(1)
- A "seen" set, a frequency map, a copy of the array O(n)
- A DP table over two dimensions O(n × m)
- A counting array over the 26 letters O(1)26 never grows with n, so it counts as a constant.
The trap nobody mentions
Every recursive call parks a frame on the call stack. That is real memory, even when your function allocates nothing at all.
Measured: Python's default recursion limit is 1,000. Depth 900 is fine; at about 1,000 it raises RecursionError — so this function dies on a list of 1,000,000 before it adds a thing. Java throws StackOverflowError the same way, at a depth that depends on the JVM stack size. Merge sort recurses O(log n) deep; quicksort's worst case is O(n) deep; DFS over a million nodes needs an explicit stack, not recursion.
Six traps that cause TLE
Every number below was measured on a normal laptop with Python 3.14. Your machine will differ; the ratios will not.
The ten-second test. Look at the innermost line of your loop. If it touches the whole collection — a slice, a sort, a search, a join, a copy — then your O(n) loop is quietly O(n2).
Six traps, continued
If your code times out in a test, do not rewrite it from scratch. Read the innermost line first. Five times out of six it is one of the six above, and the fix is a single line.
Want this on your phone?
Everything above, as a PDF built to read on a phone the morning of the interview. It costs nothing — we ask for an email so we can send it, and that is all.