1 1 vote If in this question, if we were asked to find the nth smallest number, then what would have been the answer? Data Structures + – Ajit J 862 views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply Shamim Ahmed commented Jan 2, 2019 reply Follow flag O(n) 0 0 replyShare Ajit J commented Jan 2, 2019 reply Follow flag But how brother? 0 0 replyShare Shamim Ahmed commented Jan 3, 2019 reply Follow flag 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 replyShare Ajit J commented Jan 3, 2019 reply Follow flag What an answer brother. Thanks 0 0 replyShare Please log in or register to add a comment.
0 0 votes I think (n logn) aimhigh answered Jan 2, 2019 aimhigh comment Share Follow See 1 comment 1 1 comment reply Ajit J commented Jan 2, 2019 reply Follow flag How? 0 0 replyShare Please log in or register to add a comment.
