GATE CS 2008 Q47 — Asymptotic Worst Case Time and Space Complexity

To insert $n$ additional elements into an existing binary heap of size $n$, we have two main approaches:

1. One-by-one Insertion: If we insert the $n$ elements one after another, each insertion takes $O( ext{log } k)$ time, where $k$ is the heap size. For $n$ insertions, the total time complexity would be: $$\sum_{k=n}^{2n-1} \Theta(\log k) = \Theta(n \log n)$$
2. Batch Insertion (Build-Heap): Since we do not need to maintain the heap property after each individual insertion (as indicated by "not necessarily one after another"), we can:
   • Append the $n$ new elements to the end of the existing heap array in $O(n)$ time.
   • Run the standard bottom-up Build-Heap algorithm on the combined array of size $2n$.
   The time complexity of building a heap of size $N$ from scratch is $\Theta(N)$. Here, $N = 2n$, so the total time required is: $$\Theta(2n) = \Theta(n)$$

Since we seek the most efficient method to achieve the final heap, the optimal total time required is $\Theta(n)$.