O(n) for both.

The Gateway to Computer Science Excellence

+6 votes

In a min-heap with n elements

1). The 7th smallest element can be found in time, if duplicates are allowed ?

2). The 7th distinct smallest element can be found in time, If duplicates are allowed ?

1). The 7th smallest element can be found in time, if duplicates are allowed ?

2). The 7th distinct smallest element can be found in time, If duplicates are allowed ?

0

For 2nd one , O(n) is right, as we have to use hashtable .

For 1st, O(lgn) is given . I think it should be O(1) .

For 1st, O(lgn) is given . I think it should be O(1) .

+1

Ohh ... yes ... if we have elements like - 1,2 ,3,3,4,4,5,5,5,6,6,6,7

And ans for 1st is 5 and for 2nd it is 7 then you are correct...

And ans for 1st is 5 and for 2nd it is 7 then you are correct...

+1 vote

For first one :

O(log n)

Reason : To delete an element , it takes O(1), then we have to heapify , which takes O(log n);

Now for 7th smallest element, we need 7 such operations, hence O(7 log n) = O(log n)

For 2nd one :

O(n)

O(log n)

Reason : To delete an element , it takes O(1), then we have to heapify , which takes O(log n);

Now for 7th smallest element, we need 7 such operations, hence O(7 log n) = O(log n)

For 2nd one :

O(n)

0

@kapilp

are you sure for first one it is O(logn)

If we will go with simple procedure like 1+2+3+....2^n-1 comaprison to find nth smallest element then it is O(1)

another one is start deleting the element till kth level to reach the kth smallest element which is O(logn)

because everywhere I am seeing O(1) as well O(logn) time...can u plz confirm?? even I am bit confuse

see this:

https://gateoverflow.in/5915/complexity-finding-smallest-element-already-constructed

http://stackoverflow.com/questions/21600312/searching-the-7th-largest-element-in-a-max-heap

52,345 questions

60,497 answers

201,858 comments

95,315 users