Register

time complexity

• recategorized by
326 views
1 votes
1 votes
To find the kth smallest element in the heap , the time required is O(n), where k is less than the number of element in the heap. is this statement true should not it be O(klogn)
• recategorized by
User Avatar

1 Answer

Best answer
1 votes
1 votes
kth smallest element in max heap will take O(n) time as it will be one of the  leaf nodes,

kth smallest element in min heap will take O(1) time, i.e, O(klogk),which is a constant.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

471
views
1 answers
0 votes
Kaluti asked Oct 14, 2017
471 views
time complexity
time taken to delete a node from min heap if you know the value but not positionTo find the position of the number in min heap should not be log(n)why is it so O(n)
User Avatar
3.8k
views
5 answers
11 votes
Vikrant Singh asked Dec 28, 2014
3,779 views
What is the complexity of finding 50th smallest element in an already constructed binary min-heap?
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
User Avatar
1.2k
views
1 answers
1 votes
Monisha asked Oct 29, 2014
1,198 views
What will be the complexity to find the 7th smallest element in a heap?
User Avatar
1.6k
views
1 answers
4 votes
Gaurab Ghosh asked Jan 18, 2017
1,556 views
Time to build a heap
If you are given a sorted list with n elements in ascending order. Then what will be the Time complexity to build a Min heap from the given array?
User Avatar
Link Copied!