Let \(H\) be a binary min-heap consisting of \(n\) elements implemented…
2021
Let \(H\) be a binary min-heap consisting of \(n\) elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in \(H\) ?
- A.
\(\theta (1)\) - B.
\(\theta (log \ n)\) - C.
\(\theta (n)\) - D.
\(\theta (n \ log \ n)\)
Attempted by 430 students.
Show answer & explanation
Correct answer: C
Key idea: the maximum element in a binary min-heap must be at a leaf.
Leaf indices in the array representation are floor(n/2)+1 through n, so there are about n/2 leaves = Θ(n).
An optimal algorithm scans all leaves (or the whole array) once, keeping track of the maximum; that takes Θ(number of leaves) = Θ(n) time.
Lower bound: the maximum could be any leaf, so in the worst case an algorithm must inspect all those elements and cannot do o(n).
Therefore the worst-case time complexity of an optimal algorithm to find the maximum in a binary min-heap is Θ(n).
A video solution is available for this question — log in and enroll to watch it.