Cormen Edition 3 Exercise 12.1 Question 5 (Page No. 289)

Question

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.

Comments

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)$

Answer 1

If it is not O(nlgn), we can find a conflict. We know it takes O(n) time to inorder print elements in a BST. If the lower bound in the worst case in the comparison model is better than O(nlgn), then we can utilize this to give a better algorithm.

Source: https://github.com/gzc/CLRS/blob/master/C12-Binary-Search-Trees/12.1.md