data structure

Question

to find the maximum elements in a min heap represnted by an array can be computed in ____________ time

a. theta n

b.theta n2

c.theta nlogn

d.theta 1

Comments

theta (n) .

---

It is theta(n)

Answer 1

In a min-heap, the largest element will be present in one of the leaves of the heap. Since there can be n/2 leaves, we need to perform a search in those n/2 leaves, the search will have to be linear.

So, the best we can get is $\theta (n)$