Made Easy Test Series

Question

In a max heap of n elements, the time complexity to find 10^th largest element is:

a)Θ(n log n)

b)Θ(n)

c)Θ(1)

d)Θ(log n)

 

I personally think it should be Θ(n), as the 10^th largest element can be anywhere in the heap, all the elements need to be traversed once to decide that.

Answer 1

The answer must be O(logn). The simple time complexity to find K ^th largest element from a max heap is O(K*logn). For 10 it will be O(10*logn), so answer must be D. The time complexity can be O(n), but that would be a naive approach and this is a much optimised approach!
However under no circumstance can the time complexity be O(1). 
So answer must be D.

Answer 2

D is answer

extract out max 10 times , and extract max take O(log n) *10 time = O(log n)

Answer 3

Answer – C

In a max heap, the largest element is at the root, and each parent node is greater than or equal to its child nodes. Therefore, the 10th largest element in a max heap will be the 10th element when the heap is traversed in descending order.

The time complexity to find the 10th largest element in a max heap is Θ(1). This is because you can directly access the element at the 10th position in the heap without traversing the entire heap or performing any additional operations.

So, the correct option is: Θ(1)

Comments

In these two max heaps, if I want to find the k^th largest element (say 4) then in case 1 I have to traverse only two nodes (7) but for the same thing in case 2 that is going to be 4 traversals $\approx$ ceil(log 15) or Θ(log n).

My point is, even to decide whats the descending order, you need to know ALL the elements of the heap. Should take Θ(n)

---

Even if we reduce it to an approach where we just keep popping the root k times to get k-th element, and apply heapify of Θ(log n) k times, we still have to at least have Θ(log n) complexity.