Time to BUILD-MAX-HEAP on n elements — and the classic wrong answer?

Answer

Θ(n); the classic trap answer is Θ(n lg n).

Bottom-up MAX-HEAPIFY costs Σ over heights of (nodes at height h)·O(h) = O(n·Σ h/2ʰ) = O(n). Only if you bound each of the n heapify calls by lg n do you get the loose Θ(n lg n).