+1 vote
85 views
Argue that since sorting $n$ elements takes $\Omega (n\ lgn)$ time in the worst case in the comparison model, any comparison-based algorithm for constructing a $BST$ from an arbitrary list of n elements takes $\Omega (n\ lgn)$ time in the worst case.
| 85 views
+3
If there was any method which was more efficient (say O(n)), then we could build the tree in O(n) and then do an inorder traversal in O(n), thus sorting the array in O(n), which is a contradiction. Hence, any method to build a BST will take at least $\Omega(n \log n)$