Appendix A — Complexity and Correctness Field Guide

A.1 Growth rates worth recognizing

Complexity Typical interview pattern Practical meaning
\(O(1)\) direct lookup/update independent of input size
\(O(\log n)\) binary search, balanced heap operation halves/doubles a search scale
\(O(n)\) one scan, BFS/DFS proportional to input
\(O(n\log n)\) comparison sorting common cost of imposing order
\(O(n^2)\) all pairs, fixed item + scan often acceptable for pair/triple problems
\(O(2^n)\) include/exclude subsets becomes infeasible quickly
\(O(n!)\) permutations only small \(n\)

Drop constants and lower-order terms, but define variables. “\(O(n)\)” is incomplete for Course Schedule if n might mean courses but edges can be much larger; say \(O(V+E)\).

A.2 The twenty at a glance

Problem Time Working space Dominant reason
Two Sum expected \(O(n)\) \(O(n)\) map each prior value
Merge Intervals \(O(n\log n)\) \(O(n)\) output refs sort then scan
Longest Substring expected \(O(n)\) \(O(u)\) one pass + last-seen map
Valid Parentheses \(O(n)\) \(O(n)\) unmatched openers
Binary Search \(O(\log n)\) \(O(1)\) halve candidates
Three Sum \(O(n^2)\) \(O(1)\) excluding output/sort one scan per fixed value
Group Anagrams \(O(nk\log k)\) \(O(nk)\) sort characters per word
Top K Words \(O(n+u\log k)\) \(O(u+k)\) count + bounded heap
Maximum Subarray \(O(n)\) \(O(1)\) compressed DP
Product Except Self \(O(n)\) \(O(1)\) excluding output two passes
Rotated Search \(O(\log n)\) \(O(1)\) discard one half
Reverse List \(O(n)\) \(O(1)\) visit each node
List Cycle \(O(n)\) \(O(1)\) two pointers
Merge Lists \(O(n+m)\) \(O(1)\) consume every node
Level Order \(O(n)\) \(O(w)\) excluding output BFS frontier
Validate BST \(O(n)\) \(O(h)\) recursive path
LCA \(O(n)\) \(O(h)\) recursive path
Islands \(O(rc)\) \(O(rc)\) worst case visit every cell
Course Schedule \(O(V+E)\) \(O(V+E)\) adjacency representation
Coin Change \(O(ac)\) \(O(a)\) each coin per amount

Variables: \(u\) distinct characters/words as context dictates, \(k\) maximum word length or requested top count, \(w\) tree width, \(h\) tree height, \(r/c\) grid dimensions, \(V/E\) graph vertices/edges, and \(a/c\) target amount/coin count.

A.3 Auxiliary space versus output

Say which convention you use. Product Except Self is \(O(1)\) auxiliary space because its required output array is used as working storage, but the returned array still occupies \(O(n)\) memory. Three Sum may return \(O(n^2)\) output in some generalized target variants even when its pointer state is constant.

Recursive algorithms use stack space. A balanced tree often has \(h=O(\log n)\), while a skewed tree has \(h=O(n)\).

A.4 Amortized and expected costs

HashMap lookup is expected \(O(1)\), not an unconditional worst-case promise. ArrayList.add is amortized \(O(1)\) because occasional resizing copies existing elements. These qualifications show precision without derailing the interview.

A.5 A compact correctness proof

Most interview proofs need four sentences:

  1. Define state: what does each pointer, table entry, or collection mean?
  2. Initialize: why is that meaning true before work begins?
  3. Preserve: why does one iteration/recursive step keep it true?
  4. Terminate: why does the final state imply the returned answer?

For greedy-looking pointer moves, also explain why discarded candidates cannot be part of an answer. For dynamic programming, define the state and show that the recurrence covers every possible final choice.

A.6 Numeric pitfalls

  • midpoint: low + (high - low) / 2, not (low + high) / 2;
  • comparator: Integer.compare(a,b), not a - b;
  • sums/products: ask whether int overflow is within contract; use long if not;
  • sentinels: choose a value that will not overflow when the recurrence adds to it.