GATE CSE 2008 | Question: 47

Question

We have a binary heap on $n$ elements and wish to insert $n$ more elements (not necessarily one after another) into this heap. The total time required for this is

• A. $\Theta(\log n)$

• B. $\Theta(n)$

• C. $\Theta(n\log n)$

• D. $\Theta(n^2)$

Comments

https://stackoverflow.com/questions/5057562/how-is-make-heap-in-c-implemented-to-have-complexity-of-3n

---

Basically we are adding the new n elements to the heap and calling the buidlheap function. which will take O(n) time.

---

Right.

Answer 1

The worst case time complexity for insertion in a binary heap is O(Logn) (Refer Wiki). So inserting n elements in a heap of size n should take Θ(nlogn) time.
But choice (B) seems to be more appropriate answer. One of the solution of O(n) complexity can be to take the ‘n’ elements of the heap and other ‘n’ elements together and construct heap in O(2n) = O(n)

Answer 2

Answer is (B). 

We can imagine that these first 'n' elements are also not a heap. And then simply add these next 'n' elements at the end of the array. And consder total 2n elements in an array and then call Build Heap(). We know that build heap takes O(n) times. So for these 2n elements it will also takes O(n) times. So is the answer.

Answer 3

(B.) Exact analysis of Heap Would be O(n)