Complexity Analysis Questions and How to Answer Them Out Loud

Complexity questions score the reasoning path from code to answer, not the final Big O letter, and there is a fixed order worth speaking in.

Complexity analysis questions are scored on the path a candidate walks out loud from the code to the final answer, not on whether the letter at the end is O(n) or O(n log n), because two candidates can land on the same correct letter while one of them understood nothing about why it was correct. Four situations expose this most clearly: a loop whose true cost depends on an early exit condition, a recursive algorithm whose cost depends on a recurrence rather than a single pass, a resizing structure whose worst single operation looks expensive until it is averaged, and a hash-based lookup whose average and worst case diverge sharply.

An interviewer who wanted only the final complexity class could get it faster from a written answer than from forty minutes of conversation. What a live interview adds is the chance to hear a candidate name the operation that dominates, check it against the input size that actually grows, and catch their own mistake before finishing the sentence, which is the exact skill needed a year later when reviewing a colleague's design under time pressure rather than a textbook problem.

A candidate who states that the outer loop runs n times, the inner loop runs up to n times depending on the outer index, so the total number of inner iterations is n choose two and the running time is Theta of n squared, has demonstrated far more than one who says two nested loops so O(n squared), even though both reach the identical final answer. Firms grading heavily on reasoning, Two Sigma among them by reputation, weight the first answer well above the second.

Consider scanning a sorted array of price levels from the best price outward until a level with insufficient size to fill an order is found. A candidate who says this is O(n) because it is a single loop over the array has ignored that the loop usually exits after a handful of levels in a liquid book, and the honest statement out loud is that the worst case is O(n), reached only when every level must be checked, while the typical case in a liquid book is closer to O(1) because the first few levels almost always satisfy the order.

Saying both bounds out loud, worst case and typical case, and naming the condition that separates them, such as book depth or fill probability at the best price, is exactly the reasoning path the interviewer is listening for, and it heads off the natural follow-up asking what happens in an illiquid name before the interviewer has to ask it.