Algorithm Analysis for Coding Interviews

Understanding algorithm analysis is crucial for coding interviews, as it involves evaluating time and space complexity using Big O notation. Time complexity assesses how an algorithm's running time increases with input size, while space complexity measures additional memory usage. Common complexities include O(n) and O(n log n) for time, and O(1) or O(n) for space. Candidates should articulate trade-offs between time and space, demonstrating awareness of performance implications. Amortized complexity is also important, particularly for operations like appending to Python lists. Clear communication of complexity analysis is essential during interviews to showcase problem-solving skills.

We'll cover the following...

What Big O measures
- Time complexity and space complexity
Common time complexity classes
Time vs. space trade-offs
Amortized complexity
- Most common Python operations
How to analyze your own solution

Every data structure chapter in this course references time and space complexity. It is the language of coding interviews. Every time we choose a hash table over an array, or a heap over a sorted list, 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 array 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.

Complexity	Name	Example	Interview context
O(1)	Constant	Array index access, hash table lookup	The best possible. Always mention when achieved.
O(log n)	Logarithmic	Binary search, BST operations	Excellent. Halving the search space on each step.
O(n)	Linear	Single array scan, DFS, BFS	Standard target for most interview problems.
O(n log n)	Linearithmic	Sorting, heap operations on n elements	Acceptable. Often, the best achievable solution for sorting problems.
O(n²)	Quadratic	Nested loops, bubble sort	Usually, the brute force. Mention it and optimize from here.
O(2ⁿ)	Exponential	Recursive subsets, naive recursion	Almost always too slow. A signal that memoization is needed.

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 array on every step costs $O(n^2)$ time and $O(1)$ space. Adding a hash table 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.

How to frame trade-offs: When discussing trade-offs with an interviewer, be explicit. Say: "I can solve this in $O(n^2)$ time with $O(1)$ space, or $O(n)$ time with $O(n)$ space using a hash table. The second approach is significantly faster for large inputs. Which would you prefer?" This demonstrates that we see both options and understand the trade-off, which is exactly what senior interviewers want to hear.

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 Python's dynamic array, which is what a Python list is under the hood.

Appending to a Python list is $O(1)$ amortized. Occasionally, when the underlying array runs out of space, Python doubles the array size and copies 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 list append is $O(1)$ amortized is correct and shows awareness of the underlying implementation.

Most common Python operations

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

Operation	Time Complexity	Description
`list.append(x)`	O(1) amortized	Occasionally O(n) on resize but amortized O(1).
`list.pop(0)`	O(n)	Every element shifts left. Use `deque.popleft()` instead.
`list.insert(i, x)`	O(n)	Every element after index i shifts right.
`x in list`	O(n)	Linear scan. Use a set for O(1) membership checks.
`x in set`	O(1)	Hash-based lookup. Always prefer the list for membership.
`dict[key]`	O(1)	Average case. Worst case O(n) due to hash collisions.
`sorted(iterable)`	O(n log n)	Timsort. Always O(n log n) regardless of input order.
`deque.popleft()`	O(1)	The correct way to implement a queue in Python.

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 hash table 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)$ .

Common mistake (ignoring space complexity): Many candidates state only time complexity and forget space. Interviewers notice this. Always state both. If the space complexity is $O(1)$ , say, so explicitly, as it is often the harder constraint to achieve and worth highlighting. If the space complexity is $O(n)$ , mention what is causing it and whether it can be reduced.

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.

Interview lens: In an interview, always state the time and space complexity of your solution before the interviewer asks. Say: "This runs in $O(n)$ time and $O(n)$ space." Then briefly justify it. This signals that complexity analysis is part of your natural problem-solving process, not an afterthought.

Pattern	Space	Example
Fixed number of variables	O(1)	Two pointers, sliding window
Hash table or array of size $n$	O(n)	Frequency count, prefix sums
Recursive call stack of depth $h$	O(h)	DFS on a tree of height $h$
Storing all subsets or combinations	O(2ⁿ)	Backtracking problems

1.Introduction

2.Algorithm Analysis for Interviews

3.Arrays

4.Linked Lists

5.Stacks

6.Queues

7.Heaps & Priority Queues

8.Hashing

9.Introduction to Trees

10.Introduction to Graphs

11.Trie

12.Interview Readiness and Strategy

Mock Interview