Ask a candidate to swap a nested loop for a hash map, and most can do it. Ask them why that change drops the runtime from O(n²) to O(n), and the room goes quiet. That gap, not the code itself, is what separates a strong technical round from a shaky one. Big-O time complexity is the language interviewers use to talk about that gap, and it's a lot more specific than "how fast is it."
What Big-O time complexity actually measures
Big-O describes how the runtime (or memory) of an algorithm grows as the input size, usually written n, gets arbitrarily large. It's not a stopwatch measurement. It's a shape. The NIST Dictionary of Algorithms and Data Structures defines it formally: f(n) = O(g(n)) means there exist positive constants c and k such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ k. Stripped of the math notation, that says: past some point, f never grows faster than a constant multiple of g. Everything before that point doesn't count.
That last part does a lot of quiet work. Big-O throws away constant factors, so a loop that does 3n operations and one that does 300n operations are both, technically, "O(n)." It throws away lower-order terms, so O(n² + n) collapses to O(n²), because the n² term dominates once n gets big enough. And it says nothing about small inputs. An O(n²) solution can easily beat an O(n log n) one when n is 12, because the crossover point depends on exactly those constants Big-O just deleted. If a problem caps the input at, say, 15 or 20 elements, saying so out loud, and picking the simpler O(n²) approach on purpose, tends to read better than reaching for a more complex algorithm nobody asked for.
How to derive the complexity of a snippet, step by step
Most candidates don't derive Big-O, they pattern-match. "I see a loop, so it's O(n)." That gets you through easy problems and falls apart the moment two loops interact, or a loop hides inside a function call. The actual method is duller than people expect: count the operations, drop the constants, keep the term that dominates.
for i in range(n): # runs n times
for j in range(n): # runs n times, for EACH i
check(arr[i], arr[j]) # O(1) work per call
# total operations: n * n = n^2 -> O(n^2)Swap the inner loop for a set lookup and the shape of the whole function changes:
seen = set()
for num in nums: # runs n times
if target - num in seen: # O(1) average
return True
seen.add(num) # O(1) average
# total operations: n * O(1) -> O(n)Three rules cover nearly everything you'll see in a coding round. Sequential blocks add: a loop of n followed by a separate loop of m gives O(n + m), which simplifies to O(max(n, m)). Nested loops multiply: an n loop inside an n loop is O(n²), never O(2n), no matter how tempting that shortcut looks. And a loop that cuts the remaining problem in half each pass, instead of walking through it linearly, is O(log n) regardless of how large n starts out. Recursion is where this method stops being a line-count exercise. You can't just tally the loop, you need to know how many times the function calls itself and how much work each call does on top of its children, which is usually solved with a recurrence relation rather than eyeballing the code.
The complexity classes worth knowing cold
Interviewers rarely ask you to define Big-O. They expect you to recognize which class a given pattern falls into, on sight, and explain why. Here are the seven that show up constantly, each with a concrete example instead of an abstract description.
| Class | Name | Real example |
|---|---|---|
| O(1) | Constant | Array index lookup (arr[5]), hash map get on average |
| O(log n) | Logarithmic | Binary search on a sorted array; height of a balanced BST |
| O(n) | Linear | Single pass through a list; the hash-set two-sum above |
| O(n log n) | Linearithmic | Merge sort, heap sort, Python's built-in sorted() |
| O(n²) | Quadratic | Nested loops comparing every pair; bubble sort, insertion sort |
| O(2ⁿ) | Exponential | Naive recursive Fibonacci with no memoization; generating a power set |
| O(n!) | Factorial | Brute-force permutations of n items; naive traveling-salesman |
The jump from n² to n! is bigger than the table makes it look. At n = 20, n² is 400, a laptop clears that instantly. 2ⁿ at n = 20 is about a million, still fine. n! at n = 20 is roughly 2.43 × 10¹⁸, which no computer built today finishes in your lifetime. That's the entire reason interviewers care about this at all: past a certain n, the class you picked matters more than every optimization you'll ever make inside it.
Best case, worst case, and the amortized case people get wrong
Quicksort's average case is O(n log n) and its worst case is O(n²), and both numbers are correct at the same time, they're just describing different inputs. Best case describes the friendliest possible input (already-sorted data for insertion sort: O(n)). Worst case describes the input that hurts most (a pivot that's always the smallest element for quicksort: O(n²)). Average case is the expected runtime across random inputs, which is the number most interviewers actually want when they ask "what's the complexity."
Amortized is a different animal, and candidates conflate it with average case constantly. Average case is a statement about probability across possible inputs. Amortized is a guarantee about a sequence of operations on the same structure, no randomness involved. A dynamic array's append is a textbook case: most appends are O(1), but occasionally the array is full and has to be copied into a bigger one, which costs O(n). Spread that occasional O(n) cost across all the O(1) appends that happen between resizes, and the average cost per append works out to O(1), guaranteed, not just likely. Python documents this directly: list append is O(1) amortized worst case, according to the language's own complexity reference. Say "amortized" instead of "average" in an interview and you'll usually get a small nod. Mix them up and a sharp interviewer will ask a follow-up you don't want.
Space complexity is the question that catches people who nailed the time analysis
Space complexity measures extra memory an algorithm uses beyond the input itself, and it's easy to forget because it doesn't show up as an explicit data structure. Recursive functions are the classic trap. A recursive factorial function looks like it uses no extra memory, no array, no hash map, but every call sits on the call stack until it returns, so a recursion that goes n levels deep costs O(n) space even with zero variables declared. Rewrite the same function iteratively with a loop and the space drops to O(1), while the time complexity stays exactly the same.
Memoization makes the trade-off explicit in the other direction. Naive recursive Fibonacci is O(2ⁿ) time and O(n) space (call stack only). Add a cache and it drops to O(n) time, but the space cost also becomes O(n), because now you're storing every subproblem's answer. Faster in time, heavier in memory. Interviewers who ask "can you do this in-place" are really asking whether you noticed you were about to pay for that speed with space, and whether you can say which trade-off you're choosing on purpose.
The data-structure cheat sheet interviewers assume you've memorized
Nobody expects you to derive these from scratch mid-interview. They expect you to already know them, the same way you know your own phone number.
| Structure / operation | Average | Worst case |
|---|---|---|
| Array/list: index by position | O(1) | O(1) |
| Array/list: append at end | O(1) amortized | O(1) amortized worst |
| Array/list: insert at front | O(n) | O(n) |
| Hash map: get / set | O(1) | O(n), on heavy collisions |
| Set: contains / add | O(1) | O(n), on heavy collisions |
| Balanced BST: search / insert | O(log n) | O(log n) |
| Linked list: prepend | O(1) | O(1) |
| Linked list: search by value | O(n) | O(n) |
The hash map row is the one worth sitting with. Python's own documentation lists dictionary get and set as O(1) on average but O(n) amortized worst case, because a bad hash function or an adversarial input can collapse a hash table into something closer to a linked list. Most interviewers won't press you on this. A few will, especially at companies that care about systems-level thinking, and being able to say "average O(1), degrades under collisions" instead of a flat "O(1)" signals you understand the structure isn't magic. For a deeper walkthrough of when to reach for which structure, our data structures interview guide goes through the decision process problem by problem.
How to actually say this out loud without freezing
Here's a pattern we keep seeing in mock interview transcripts on LastRoundAI: candidates get the final Big-O right, then get asked "why," and stall. They know the answer, not the derivation, and under pressure those aren't the same skill. The fix isn't memorizing more classes. It's narrating out loud, every time you practice, using roughly this shape: state the brute-force complexity first, name what's slow about it (usually a nested loop or repeated linear search), state the optimized complexity, and name the trade-off, whether that's extra space, extra constant factor, or lost simplicity.
That narration habit is exactly what LastRoundAI's AI interview copilot is built to reinforce in the moment: it listens through a live technical round and surfaces a quick, sub-200ms complexity read as you talk through your approach, so you can check your own reasoning against it rather than freezing mid-sentence. It won't replace knowing the seven classes above. It's there for the moment you're staring at a whiteboard and the "why" you knew an hour ago has gone quiet. Once the pattern recognition is solid, most of what's left is repetition, and our coding pattern cheat sheet is a reasonable place to drill the shapes that keep showing up.
One honest caveat: none of this tells you whether a specific company still asks pure complexity-analysis questions in 2026, some have moved toward system design and take-homes instead. But if you get a live coding round, the interviewer almost always wants the Big-O said out loud, unprompted, before they ask for it. That's usually the easiest point in the whole interview to pick up, and it's the one candidates leave on the table most often. If you're rounding out the rest of your prep kit at the same time, our free interview tools cover the parts of getting hired that sit outside pure algorithms, resumes, cover letters, that kind of thing.