The tight asymptotic time complexity of building a heap from an array of n…
2010
The tight asymptotic time complexity of building a heap from an array of n elements using the standard bottom-up BUILD-HEAP procedure is
Answer: C. O(n) — Concept: In an array-based heap, bottom-up BUILD-HEAP applies sift-down only to internal nodes. A node at height h needs at most O(h) sift-down work, and the…
- A.
O(1)
- B.
O(log n)
- C.
O(n)
- D.
O(n log n)
Attempted by 87 students.
Show answer & explanation
Correct answer: C
Concept: In an array-based heap, bottom-up BUILD-HEAP applies sift-down only to internal nodes.
A node at height h needs at most O(h) sift-down work, and the number of nodes at that height is O(n/2(h+1)).
Application: Sum the work over all heights: Σ from h = 0 to log n of (n/2(h+1)) × O(h).
Factor out n. The remaining series Σ h/2(h+1) converges to a constant, so the total is O(n).
Cross-check: Repeatedly inserting n elements can take O(n log n), but that is a different construction method.
Therefore, the tight asymptotic complexity of standard bottom-up heap construction is Θ(n), represented by O(n) among the given options.