Time Complexity & Big-O for Interviews, Explained

"What's the time complexity?" is the most predictable follow-up in any coding interview, and freezing on it can sink an otherwise-correct solution. The good news: you don't need heavy math. You need to recognise a handful of shapes and reason out loud. Here's the practical version.

Big-O describes how your runtime grows as the input grows, not the exact time. Interviewers care that you can estimate it and talk through the trade-off, not that you memorised a proof.

The complexities you'll see

Big-ONameTypical source

O(1)ConstantHash-map lookup, array index
O(log n)LogarithmicBinary search, balanced-tree ops
O(n)LinearOne pass over the input
O(n log n)LinearithmicGood sorting, divide-and-conquer
O(n²)QuadraticNested loops over the same input
O(2ⁿ)ExponentialNaive recursion / subsets / brute force

How to analyse on the spot

• Count the loops. One pass = O(n). A loop inside a loop over the same data = O(n²).

• Halving = log. If each step cuts the problem in half (binary search), that's O(log n).

• Recursion = branches^depth. Two recursive calls per level, n levels deep, tends toward O(2ⁿ) unless you memoise.

• Don't forget space. An extra hash map or recursion stack is O(n) space; interviewers ask about both.

What interviewers want

State your complexity, then say why ("it's O(n) because I do a single pass and the hash-map lookups are O(1)"). If your brute force is O(n²), name it and mention the better approach even if you don't code it; showing you see the optimisation often matters as much as writing it.

Complexity is the language tying every pattern together, and the DSA patterns cheat sheet shows which patterns hit which complexity. Avoid the usual slip-ups in common coding interview mistakes, and when you're ready to practise by role, DSA Tracker orders the right problems first.

Five problems where the complexity is the whole interview

Each of these is asked because the brute force is obvious and the interviewer wants to see you name it, cost it, and then improve it. Two Sum: O(n squared) with nested loops, O(n) with a hash map, and the follow-up is what you traded for that speed (O(n) space). Contains Duplicate: O(n squared), then O(n log n) by sorting, then O(n) with a set, and a good answer mentions all three. Maximum Subarray: the O(n cubed) triple loop, the O(n squared) prefix version, and Kadane's single pass. Binary Search and Search in Rotated Sorted Array: the moment you say "the array is sorted" the interviewer expects O(log n), and the rotated variant checks whether you can keep it. Merge Intervals: O(n log n) because sorting dominates and the merge pass is linear, which is the standard example of a sort being worth its cost. If you want to see the operation count rather than reason about it, the tracer steps through your own solution and shows every iteration.

Related on DSA Tracker

• The 15 DSA patterns
• Binary Search topic hub
• Sorting topic hub
• Two Sum: O(n squared) to O(n)
• Trace your own code line by line

Further reading: Binary search on Wikipedia.