Question

In a binary max heap containing n numbers, the smallest element can be found in ______ time.  
1. O(n)
2. O(log₂ n)
3. O(1)
4. O(log₂ log₂ n)

Answer 1

Correct Answer - Option 1 : O(n)

The correct answer is option 1.

• The heap's smallest values will always be present on the last level or second last of the heap in a MAX heap, and the time complexity of reaching the last level of the heap is O(n).
• We must use a linear search to search all of the elements in order to find the smallest element and heap.
• It will take O(n) time to traverse all of the elements using linear search. 

Hence the correct answer is O(n).