Time & Space Complexity
Time complexity is how runtime grows with input size (e.g. doubling the input).
Space complexity is the extra memory (beyond the input) the algorithm uses.
We use Big O notation for how cost grows as input gets large (constants and lower-order terms are dropped).
Common Complexity Classes
Section titled “Common Complexity Classes”From fastest to slowest (for large n):
- O(1) — Constant: same cost regardless of input size (e.g. hash lookup, array index).
- O(log n) — Logarithmic: cost grows slowly (e.g. binary search, balanced tree operations).
- O(n) — Linear: one pass over the input (e.g. single loop, BFS/DFS over n nodes).
- O(n log n) — Linearithmic: typical for efficient sorting (e.g. merge sort, quicksort average).
- O(n²) — Quadratic: nested loops over the same input (e.g. insertion sort, some DP).
- O(2^n) or exponential — Cost doubles (or worse) as input grows (e.g. naive recursion, some backtracking).
- O(V + E) — Graph input: linear in vertices plus edges (e.g. BFS, DFS on a graph).
Actual complexity depends on the problem variant; the table below is a typical summary for the topics we cover.
Summary by Algorithm
Section titled “Summary by Algorithm”| Algorithm | Time | Space |
|---|---|---|
| Two Pointers | O(n) | O(1) |
| Sliding Window | O(n) | O(1) or O(k) |
| Prefix Sum | Build O(n), query O(1) | O(n) |
| Breadth-First Search | O(V + E) or O(n) | O(n) |
| Depth-First Search | O(V + E) graph; O(n) tree | O(h) recursion stack (height or depth) |
| Binary Search | O(log n) | O(1) |
| Heap | O(log n) per insert/extract | O(n) |
| Backtracking | Often exponential | O(depth) |
| Dynamic Programming | Often O(n²) or O(n·W) | Proportional to state |
| Divide and Conquer | e.g. O(n log n) | O(log n) |
| Trie | O(m) per string (length m) | O(total characters) |
| Union Find | O(α(n)) per operation | O(n) |
| Greedy | Often O(n log n) + O(n) | O(1) or O(n) |
Each topic page has a Time / space line with more detail and context for that algorithm.