Time complexity analysis

Question

What will be the time complexity if fractional knapsack is implemented using min heap instead of sorted array

a) O(nlogn)

b)O(n^2)

c)O(n)

d) none of these

Answer 1

Answer : A (Assuming in the Question He meant Just Heap or Max Heap)

First we will find $p_i/w_i$ for each item which will take $O(n)$ time.

Then, We will build a Max Heap (not Min Heap) based on parameter $p_i/w_i$ which will take $O(n)$ time.

then we will delete the Root(max item) one by one ($O(logn)$ time) and do some calculation ($O(1)$ time). So, for $n$ items, $O(nlogn)$ time.

---

but If we implement it with min heap data structure then $O(n^2)$. Because It takes $O(n)$ to find max in Min-heap.

Comments

Will it be O($n^{2}$logn)? To find max in min heap we need O(n) time because max will be leaf at last level after that heapify needs to be called which will take O(logn) time. So for n items it will be O($n^{2}$logn)

---

@Shubhgupta

I have also thought  in your ways but

To find max and do the heapify it will take

O( n + log n) for 1 element{ n to find max and log n to do the heapify}

 instead of O(n*logn).

So for n element time complexity will be

n*O(n+logn)=O(n^2)

---

oh yes wrongly calculated! Thanks