Question

One way to build a heap is to start at the end of the array (the leaves) and push each new value up to the root. Its time complexity is _______ .

• A. O(n)
• B. O(\log n)
• C. O(n \log n)
• D. O(n\(^2\) \log n)

Hint:

Building a heap using insertions takes \(O(n \log n)\), but there is a more efficient approach that takes \(O(n)\) time by using the heapify method.

Answer 1

The Correct Option is C

Building a heap by pushing each new value up to the root is essentially a sequence of insertions. Each insertion takes \(O(\log n)\) time, and we perform this for all \(n\) elements, resulting in a time complexity of \(O(n \log n)\). This is more efficient than other methods like sorting the array first, which would take \(O(n \log n)\) as well.