The smallest element in a max heap would always be in the last level. => Search all leafs.
No. of leafs = No. of internal nodes + 1.
In an asymptotic sense, we can say No. of leafs = No. of internal nodes. If total nodes = n, leafs = $O(\frac{n}{2})$ = Internal nodes.
And, $O(\frac{n}{2}) = O(n)$
So, Option A.