in DS
154 views
0 votes
0 votes

If in this question, if we were asked to find the nth smallest number, then what would have been the answer?

in DS
by
154 views

4 Comments

O(n)
0
0
But how brother?
0
0
Lets start from the root. The number of comparisons to get smallest number among root and its 2 children is 3. So O(1) time.

Secondly, to get 7th smallest number we need constant number of comparison. Hence again O(1).

Now lets extend this comparison to n levels. In that that case we might have to use a hash table and the complexity would rise up to O(n).

Hope it helps..
0
0
What an answer brother. Thanks
0
0

1 Answer

0 votes
0 votes
I think (n logn)

1 comment

How?
0
0

Related questions