218 views

Maximum element in a min-heap represented by an array, can be computed in _____  time

1. $O(n)$
2. $O(\log n)$
3. $O(n \log n)$ but not $O(n)$
4. $O(1)$

Maximum element in a min-heap can be found only at the leaf. Total number of leaf nodes in a binary heap is exactly $\lceil \frac{n}{2}\rceil$ and there is no ordering among these elements and so we need $\lceil \frac{n}{2}\rceil$ comparisons to find the maximum. Being represented in an array, we can index to all leaf nodes in constant time. Hence, our required answer is $\Theta (n)$ which also implies $O(n).$
Correct option A.

"Since we cannot be sure of the minimum no. of elements in leaf we can only use O and not Θ"  I am not getting this sentence can you please explian in detail.

for finding Max element in min heap , we can heapify heap to max heap in Log(n) , and first element will be max element.
So According to my concept it should be of O(log(n))