Question

3. N elements are inserted from a min-heap with N elements. The total running time is:

a) O(N2) worst case

b) O(logN) worst case

c) O(N) worst case          

d) None of these

Answer 1

Answer 3.)

(c) O(N) - Worst case

When N elements are inserted in a min-heap with N elements, the time complexity for this is O(LogN) - in worst case (in general). So, it will take Θ(NlogN) time.

But O(N) is the most appropriate answer.

The solution of time complexity O(N) takes the min-heap with N elements and other 'N' elements are to be inserted. It will construct min-heap in O(2N).

O(2N) can be written in the form O(N).

So, the total running time when N elements are inserted in a min-heap with N elements is O(N).