So my friend and I are not seeing eye to eye in this question. It asks for the time complexity of searching for the 7th largest element in a max-heap of n elements?
I'm of the opinion that it should be O(n) and she is of the opinion it should be O(1). My logic is that suppose n is 7 then 7th largest element will be the last element in the heap so if we consider the worst case it should be O(n). She however says that since it's a max heap so finding the 7th largest element should take constant time. But using her logic even the 50th largest element or the 100th largest element can be found in O(1) time. Also the book in which we came across this question says the solution will be O(logn).
Can someone please tell me which solution is correct?
There is an O(1) solution. Let's assume that the heap is represnted as a tree and max element is a root. Than the distance between the node with 7-th largest element and the root is less than or equal to 6. The number of nodes with distance to the root <= 6 is never greater than 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127. It is a constant. They can traversed in constant time.