Time Complexity Cheat Sheet for Interviews

Every coding interview ends the same way: "What's the time and space complexity?" Getting this wrong — or hesitating — signals that you do not fully understand your own solution. Interviewers use complexity analysis to gauge whether you can evaluate trade-offs and choose the right approach.

Big O notation describes how an algorithm's resource usage grows relative to the input size. It ignores constants and lower-order terms because what matters at scale is the growth rate, not the exact count.

O(1) — constant

The operation takes the same time regardless of input size. Examples: array access by index, hash map lookup, push/pop on a stack. If your algorithm does a fixed amount of work per element, the per-element cost is O(1).

O(log n) — logarithmic

The input is halved at each step. The classic example is binary search. Any algorithm that eliminates half the remaining candidates per iteration is O(log n). This also applies to balanced BST operations and heap insert/delete.

O(n) — linear

You examine every element once. Single-pass array traversals, hash map construction, and two-pointer techniques are O(n). Most optimal interview solutions are O(n) because you must at least read the input.

O(n log n) — linearithmic

Sorting is the prototypical O(n log n) operation. Merge sort, quicksort (average case), and heap sort all achieve this. Many problems that seem to require O(n²) can be solved in O(n log n) by sorting first, then using a linear scan.

O(n²) — quadratic

Nested loops where both iterate over the full input. Brute-force pair comparisons, insertion sort, and selection sort are O(n²). In interviews, if your solution is O(n²), look for a hash map or sorting optimization to bring it down to O(n) or O(n log n).

O(2ⁿ) — exponential

The work doubles with each additional input element. Naive recursive solutions to Fibonacci, subset generation, and the traveling salesman problem are exponential. Dynamic programming reduces many of these to polynomial time.

O(n!) — factorial

Generating all permutations of n elements. Only acceptable for very small inputs (n ≤ 10). If your solution is factorial, check if the problem actually requires examining all permutations or if there is a shortcut.

O(1) — in-place

No extra data structures proportional to input size. Two-pointer solutions, in-place sorting (like quicksort), and solutions that modify the input array achieve O(1) space. Interviewers love asking "can you do it in constant space?" — it usually means two pointers or bit manipulation.

O(n) — linear space

A hash map, hash set, or additional array of size n. Most solutions that trade space for time use O(n) space. Recursion also uses O(n) stack space when the recursion depth is n (like DFS on a skewed tree).

O(n²) — quadratic space

A 2D matrix for dynamic programming. Edit distance, longest common subsequence, and many grid DP problems use O(n×m) space. Often optimizable to O(min(n,m)) by keeping only the previous row.

Count the loops

A single loop over n elements is O(n). Nested loops are O(n²). A loop that halves the input each iteration is O(log n). A loop inside a loop that halves is O(n log n). The key is identifying how many times each loop runs relative to n.

Account for built-in operations

Sorting is O(n log n). Searching in a sorted array with binary search is O(log n). Hash map operations are O(1) average but O(n) worst case. String concatenation in a loop is O(n) per operation in languages with immutable strings, making the loop O(n²) total.

Recursive complexity

For recursion, identify the number of recursive calls and the work per call. Fibonacci with two recursive calls and O(1) work per call is O(2ⁿ). Merge sort with two recursive calls and O(n) merge work is O(n log n). The Master Theorem formalizes this for common recurrence patterns.

Array: access O(1), search O(n), insert/delete O(n). Hash map: insert/search/delete O(1) average. Binary search tree (balanced): insert/search/delete O(log n). Heap: insert O(log n), extract-min O(log n), peek O(1). Stack/queue: push/pop O(1). Linked list: access O(n), insert/delete at known position O(1).

Knowing these by heart lets you quickly evaluate whether a data structure switch improves your solution's complexity.

State the complexity of each approach you discuss, not just the final one. Explain why — "this is O(n) because we visit each element exactly once." If the interviewer asks for improvement, think about what operation is the bottleneck and whether a different data structure makes it cheaper. Phantom Coder can help you quickly verify complexity during practice sessions so you build confidence before the real interview.