Time Complexity & Big-O for Interviews — Explained Simply

"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 actually see

Big-O	Name	Typical source
O(1)	Constant	Hash-map lookup, array index
O(log n)	Logarithmic	Binary search, balanced-tree ops
O(n)	Linear	One pass over the input
O(n log n)	Linearithmic	Good sorting, divide-and-conquer
O(n²)	Quadratic	Nested loops over the same input
O(2ⁿ)	Exponential	Naive 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 actually 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.