Question

What is the time complexity of building a heap from an unsorted array of size \(n\)?

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

Hint:

A common misconception is that building a heap takes \(O(n \log n)\) because heapify is \(O(\log n)\). However, since most nodes are near the bottom of the tree and require minimal work, the total complexity becomes \(O(n)\).

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question asks for the time complexity of the standard algorithm to convert an unsorted array of \(n\) elements into a binary heap.
This is typically done using the bottom-up heap construction method, often called Floyd's algorithm or the `build-heap` algorithm.
Step 2: Key Formula or Approach:
The approach is to start from the last non-leaf node and call the `heapify` function on each node up to the root.
The cost of `heapify` on a node is proportional to its height, \(h\).
The total time complexity is the sum of the costs of `heapify` for all non-leaf nodes.
The number of nodes at height \(h\) in a complete binary tree of \(n\) nodes is approximately \( \frac{n}{2^{h+1}} \).
The total cost \(T(n)\) is given by the summation:
\[ T(n) = \sum_{h=0}^{\log_2 n} \left( \frac{n}{2^{h+1}} \right) \cdot O(h) \] Step 3: Detailed Explanation:
Let's analyze the summation for the total work done.
\[ T(n) \approx \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot c \cdot h \] Where \(c\) is a constant factor from the \(O(h)\) complexity of heapify.
\[ T(n) = \frac{cn}{2} \sum_{h=0}^{\log n} \frac{h}{2^h} \] The summation part \( \sum_{h=0}^{\infty} \frac{h}{2^h} \) is a known series that converges to a constant value (specifically, 2).
Since the sum is bounded by a constant, the total complexity is proportional to \(n\).
\[ T(n) = O(n) \] This linear time complexity arises because most nodes are near the bottom of the tree (leaves), and the `heapify` operation on them is very cheap (height is small).
Step 4: Final Answer:
The time complexity of building a heap from an unsorted array of size \(n\) using the standard bottom-up approach is \(O(n)\).