Question

The time complexity in order to build a heap of 'n' elements is ..............

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

Hint:

Building a heap is a logarithmic operation, so the time complexity depends on the number of nodes and the depth of the tree.

Answer 1

The Correct Option is A

Step 1: Understand Heap Construction.
To build a heap, the most efficient method involves starting from the last internal node and applying the heapify operation, which takes \( O(\log n) \) time. The heapify operation is applied to each node, and since there are \( n \) nodes, the total time complexity is \( O(n \log n) \).

Step 2: Conclusion.
Thus, the correct time complexity for building a heap of \( n \) elements is \( O(n \log n) \).