Interactive complexity notes that connect logarithms, tree height, heap operations, and growth-rate comparisons.
log₂(n) answers one question: how many times can you halve n before reaching 1?
This is exactly the height of a binary tree with n nodes. A tree of 1 million nodes is only 20 levels tall.
Each level of the tree doubles the number of nodes. So the height grows as the inverse of doubling — which is log₂.
| Level | Nodes at level | Total nodes so far | Height = log₂(total) |
|---|---|---|---|
| 0 (root) | 1 | 1 | 0 |
| 1 | 2 | 3 | ≈ 1.6 |
| 2 | 4 | 7 | ≈ 2.8 |
| 3 | 8 | 15 | ≈ 3.9 |
| k | 2ᵏ | 2ᵏ⁺¹ − 1 | k |
When you insert into a heap, the new element bubbles up from the bottom to its correct position. The maximum distance it can travel = the height of the tree = log₂(n).
Inserting a very small value (like 0) — worst case, it travels all the way to the root. Each arrow = one swap = one comparison.
0* was inserted at the leaf. It swapped upward 3 times = log₂(15) ≈ 3.9 → rounded to 4. That's O(log n).
If one insert costs O(log n), and you do n inserts (building a heap by pushing one element at a time), the total cost is:
See how slowly log n grows vs n and n². Drag the slider to feel the difference.
At n = 1024: n² = 1,048,576 operations. n log n = 10,240. log n = just 10. That gap is why we care about complexity.
| Operation | Why log n? | Total for n elements |
|---|---|---|
| Insert (push) | bubble up ≤ tree height | O(n log n) |
| Delete min (pop) | sift down ≤ tree height | O(n log n) |
| heapify | most nodes near leaves (short trips) | O(n) — better! |
| Heap sort | n pops, each O(log n) | O(n log n) |
heapify is O(n) not O(n log n) because it builds bottom-up — lower nodes (majority) sift down only 1–2 levels, not log n levels. The math sums to O(n).