The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
56 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 | 56 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

47,005 questions
51,326 answers
177,510 comments
66,668 users