Foundations
Summations & series
Arithmetic and geometric series that underpin merge sort and heap analysis.
Question: why is merge sort O(n log n), not O(n²)?
What looks nested is actually n work at each of log n levels. This page unpacks the gap between "sum of levels" and "sum of nested loops" via the arithmetic and geometric series. Merge sort's answer is n log n, not n².
By the numbers
| n | 1+2+…+n | ≈ n² | 1+2+4+… (log n levels) | ≈ 2n |
|---|---|---|---|---|
| 8 | 36 | 64 | 15 | 16 |
| 64 | 2080 | 4096 | 127 | 128 |
| 1024 | ~5·10⁵ | ~10⁶ | 2047 | 2048 |
The arithmetic series sits between n and quadratic; the geometric series caps at 2n. Merge sort does n work per level and has log n levels, so the total is n · log n.
Where each comes from
Arithmetic series: 1 + 2 + … + n
Two nested loops, outer 1..n, inner averages n/2: total 1 + 2 + … + n = n(n+1)/2 ≈ n²/2. Drop the constant, O(n²). This is the cost of naive double-traversal solutions (compare every pair).
Geometric series: 1 + 2 + 4 + … + 2ᵏ
Sum 2ᵏ⁺¹ - 1. Set n = 2ᵏ and it's 2n - 1 → O(n). Tree-level sizes double: 1, 2, 4, … n; their total is linear. That's why walking every level of a divide-and-conquer tree is O(n), not O(n²).
Putting them together: merge sort
The work at each level is the merging of that level's subarrays. Work per level = n. Number of levels = log₂ n (each level halves). Total: n · log n. So merge sort's "total work" islevel count × work per level, not a nested-loop product.
Trap: "all levels total n, so it can't be n log n"
This conflates one path with all levels. Walking one root-to-leaf path is O(log n) (like binary search). But merge sort visits every level in full, so n work × log n levels = n log n. "One path O(log n), the whole tree O(n)" is right for a traversal, but merge sort isn't a traversal: it's merging the whole tree.
Where to go next
- Logarithms: why log n levels is small.
- Complexity & Big-O: the practical loop-counting page.
- Growth rates: all three series on one chart.
Exercise
Scrub the chart below to n = 64. Predict the n² (arithmetic series) and n log n (merge sort) values. Now bump to n = 1024: how many times did n² grow, how many times did n log n? That gap is why interviews always push for n log n over n².