Complexity Analysis

Big-O describes how cost grows with input size, ignoring constants. It is the shared vocabulary for discussing an approach before anyone commits to implementing it, which is exactly what a phone screen is testing.

Read the shape, not the code. A loop over n is O(n). A nested loop over the same n is O(n²). Halving the search space each step is O(log n). Sorting is O(n log n) and is usually the dominant term the moment it appears. Recursion that splits into two halves and does linear work per level is also O(n log n) — that is mergesort.

Constants and the real world. O(n log n) with a tiny constant routinely beats O(n) with a huge one at realistic sizes. Big-O is about asymptotic growth; when someone says "this is O(1) but the constant is a network round trip," they are making a real and important point.

Amortised is not average. A dynamic array's push is O(1) amortised: most pushes are cheap, and the occasional resize is O(n), which averages out across a sequence. That is a worst-case guarantee over a sequence of operations, unlike hash table lookup, which is O(1) average and O(n) worst case under adversarial collisions.

Space counts too, and recursion is where people forget. A recursive solution carries O(depth) stack space even when it allocates nothing — a recursion over a linked list of a million nodes will overflow the stack while looking allocation-free.

Say the bound and the reason. "This is O(n log n), dominated by the sort" is a complete answer. Reciting a bound with no justification is the thing interviewers are checking for.