What is the tightest asymptotic time complexity for building a binary max-heap from an unsorted array of n elements?
Show answer
Θ(n)
Although inserting n elements individually would take O(n log n), the 'Build-Heap' procedure works bottom-up and summates to a linear series, making the total cost proportional to the number of elements.
Also asked as:
- What is the tightest asymptotic time complexity for constructing a binary max-heap from an unsorted n-element array?