In a binary max heap containing n numbers, the smallest element can be found…

Answer: O(n).

Key idea: the smallest element in a binary max-heap must be a leaf. There are about n/2 leaves, so scanning them to find the minimum takes Θ(n) time.

• Step 1: Identify the leaves. In the array representation (1-based indexing), leaves occupy indices ⌊n/2⌋+1 through n; in any representation there are about n/2 leaves.

• Step 2: Scan all leaf nodes once, keeping track of the smallest value seen.

• Time complexity: you examine about n/2 elements, so the running time is Θ(n) in the worst case, which is O(n).

Why other times are incorrect: constant time is impossible because the minimum is not at a fixed location; O(log n) or smaller is not achievable because those bounds apply to operations following a single root-to-leaf path, whereas finding the minimum requires checking many leaves.