Time complexity of heap for inserting element

#1

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

O(logN)

O(N)

O(NlogN)

O(N^2)
in this ans soluld be “C” but correct ans is “B”

#2

The worst case time complexity for insertion in a binary heap is O(Logn), So inserting n elements in a heap of size n should take Θ(nlogn) time.

But as given in question not necessarily one after another

so an alternative approach we can use. which requires us to insert nn elements in heap without any computation i.e. in constant time. after which we can apply Heapify operation(this operation creates heap in linear time) on the array of those element and Hence obtain a Heap in O(n)O(n) time.

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course

1 Like