O(n)

Dark Mode

0 votes

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

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..

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