Algorithm Analysis for Coding Interviews

Every data structure chapter in this course references time and space complexity. It is the language of coding interviews. Every time we choose an unordered_map over a vector, or a heap over a sorted vector, we are making a claim about performance. Big $O$ notation is how we make that claim precise, justify it to an interviewer, and compare it against alternatives.

This lesson is a focused recap of what complexity analysis means in an interview context and how to use it to make and justify decisions under pressure.

What Big O measures

Big O notation describes how the running time or memory usage of an algorithm grows as the input size grows. It is a way of comparing algorithms independent of hardware, language, and implementation details.

In an interview, Big O serves one purpose: it tells us whether our solution will be fast enough for large inputs, and it gives us a shared vocabulary to discuss trade-offs with the interviewer.

Time complexity and space complexity

Time complexity measures how the running time of an algorithm changes as the input size grows. An algorithm with $O(n)$ time complexity takes roughly twice as long when the input doubles, which tells us whether a solution will hold up on large inputs. Unless stated otherwise, we always measure the worst case: the input that causes the algorithm to do the most work.

Space complexity measures how much additional memory an algorithm uses beyond the input itself. We exclude the input because it is given to us and only measure the memory our algorithm allocates on top of it. An algorithm that allocates a new vector of size $n$ uses $O(n)$ space, while one that works with a fixed number of variables regardless of input size uses $O(1)$ space.

Common time complexity classes

These are the complexity classes that appear most frequently in coding interviews, ordered from most to least efficient.

For most coding interview problems, the target is $O(n)$ or $O(n \log n)$ time with $O(n)$ or $O(1)$ space. An $O(n^2)$ solution with $O(1)$ space is sometimes acceptable for small inputs, but always mention that you see the inefficiency and explain why you would optimize it with more time.

Common space complexity patterns

Space complexity follows the same Big O notation as time complexity, but measures memory rather than running time. The patterns below cover the space costs that appear most frequently in interview solutions.

Time vs. space trade-offs

Most interview optimizations involve trading space for time. A brute force solution that scans the vector on every step costs $O(n^2)$ time and $O(1)$ space. Adding an unordered_set or unordered_map to store previously seen values reduces the time to $O(n)$ but increases space to $O(n)$. That trade-off is almost always worth making in an interview.

The reverse trade-off, sacrificing time to save space, is less common but does appear. When an interviewer asks for an $O(1)$ space solution, they are explicitly asking us to accept slower time in exchange for constant memory. In those cases, the space constraint is the design requirement, not an afterthought.

Amortized complexity

Amortized complexity describes the average cost of an operation over a sequence of operations, rather than the worst-case cost of a single operation. It comes up most often with C++'s dynamic array, std::vector.

Appending to a vector with push_back is $O(1)$ amortized. Occasionally, when the underlying array runs out of space, the vector grows its capacity and copies or moves all elements, which costs $O(n)$. But this expensive resize happens so infrequently that, averaged over many appends, the cost per append is still $O(1)$. In an interview, saying that vector::push_back is $O(1)$ amortized is correct and shows awareness of the underlying implementation.

Most common C++ operations

These are the operations that come up most frequently in interviews and where the complexity surprises candidates.

How to analyze your own solution

In an interview, we need to analyze our solution quickly and accurately. A reliable approach is to count the loops and recursive calls, then reason about what each one does to the complexity.

A single loop over $n$ elements is $O(n)$. A nested loop where both iterate over $n$ elements is $O(n^2)$. A loop that halves the input on each step is $O(\log n)$. A recursive function that splits the input in half and makes two recursive calls, like merge sort, is $O(n \log n)$.

Space complexity follows the same logic. Count the data structures we allocate. A single unordered_map or unordered_set storing $n$ elements is $O(n)$. A recursive function that goes $h$ levels deep uses $O(h)$ call stack space. A solution that only uses a few variables regardless of input size is $O(1)$.

Complexity analysis is a tool for communication, not just calculation. The goal in an interview is not to produce a mathematically rigorous proof. It is to demonstrate that we understand how our solution scales and can discuss the trade-offs clearly. Every chapter that follows builds on this foundation.