The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
60 views
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)
asked in Algorithms by Active (1.5k points)
edited by | 60 views
0
n/logn and n?
0
I have added the options.. What's the explanation for the greatest element?

1 Answer

0 votes
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)
answered by (141 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,725 questions
52,835 answers
183,522 comments
68,662 users