NIELIT Qtn

Question

Consider there are n/logn min heap trees each of size logn. What will be the time complexity to find the smallest element and greatest element in these min heap trees respectively?

A) O(n/logn), O(n)
B) O(n),  O(n/logn)
C) O(n), O(n)
D) O(logn), O(logn)

Comments

n/logn and n?

---

I have added the options.. What's the explanation for the greatest element?

Answer 1

There are n/logn heaps... so the first or root of them is the minimum among them... comaparing roots of all n/log list will take O(n/logn)..

Now the maximum of any mean heap lies in the leaf which are logn/2 in above conditions... so total number of leaves are (n/logn)*(logn/2)=n/2.. so total time will be O(n)