Course contentsShow
← Computer Science
Lesson 597 of 2,87214. Heaps and Priority QueuesFree lesson

Build Heap Time Complexity: O(n) Proof

Mathematical analysis proving linear-time heap construction despite logarithmic operations.

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.