1 votes 1 votes It is known that every comparison based algorithm makes O(nlogn) comparisons in worst case.What implication does it have on complexity of intializing binary search tree with n elements? Pooja Palod asked Oct 14, 2015 Pooja Palod 341 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes We know that in order traversal of a binary tree can be done in $O(n)$. And if tree is BST, in order traversal gives sorted list. So... Arjun answered Oct 14, 2015 Arjun comment Share Follow See all 3 Comments See all 3 3 Comments reply Akash Kanase commented Dec 11, 2015 reply Follow Share Can you explain ? (I'm not getting what is .. after So) ! I know that Binary Search tree construction will take O(nlogn) on average, same as that of sorting ! 0 votes 0 votes Arjun commented Dec 11, 2015 reply Follow Share So, if tree construction can be done in $\omega(n \log n)$ - (see small omega), that means sorting can be done in $\omega(n \log n)$ which is not possible. 1 votes 1 votes Akash Kanase commented Dec 11, 2015 reply Follow Share Got it ! 1 votes 1 votes Please log in or register to add a comment.
