Build Heap Time Complexity: O(n) Proof
You'll learn: Why building a heap from scratch takes linear time, even though each element could require logarithmic work.
The Surprising Result
At first glance, building a heap from n elements seems like it should take O(n log n) time—after all, inserting one element takes O(log n), and we have n elements. But the bottom-up construction method you learned actually runs in O(n) time. Here's why.
The Mathematical Proof
When we build a heap bottom-up, we start from the last non-leaf node and heapify down. The key insight: most nodes are near the bottom and don't move far.
In a heap with n elements:
- About n/2 nodes are leaves (do zero work)
- About n/4 nodes are one level up (move at most 1 level)
- About n/8 nodes are two levels up (move at most 2 levels)
- And so on...
The total work is:
(n/2 × 0) + (n/4 × 1) + (n/8 × 2) + (n/16 × 3) + ...
This simplifies mathematically to: n × Σ(k/2^k) where the sum converges to 2.
So the total work is approximately 2n, which is O(n).
The Intuition
Think of stacking boxes in a pyramid. Most boxes are at the bottom and barely need adjustment. Only a few boxes near the top might need to travel far down. The vast majority of the work is trivial, making the average cost per element constant.
This is fundamentally different from inserting n elements one-by-one (which bubbles up from the bottom each time, costing O(n log n) total).
Key Takeaway: Bottom-up heap construction achieves O(n) time because most nodes are near leaves and require minimal downward movement—the work decreases geometrically as you move up the tree.