Argue that since sorting \(n\) elements takes \(\Omega(n \log n)\) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of \(n\) elements takes \(\Omega(n \log n)\) time in the worst case.

Suppose we had a comparison-based algorithm that generated a binary search tree faster than \(\Omega(n \log n)\). Performing an in-order walk of a binary search tree takes \(\Theta(n)\) time and so we could combine this hypothetical approach with an in-order walk to sort \(n\) elements in somewhere between \(\Theta(n)\) and \(\Omega(n \log n)\) time. Unfortunately, this is in direct contradiction with Theorem 8.1 which stipulates that there is no comparison-based algorithm that can sort \(n\) elements in faster than \(\Omega(n \log n)\) time. Thus any comparison-based algorithm that constructs a binary search tree must do so in \(\Omega(n \log n)\) time in the worst case.