Exercise 12.1.5

Argue that since sorting nn elements takes Ω(nlgn)\Omega(n \lg 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 nn elements takes Ω(nlgn)\Omega(n \lg n) time in the worst case.

Let's make a reductio ad absurdum argument.

Let's assume that there exists o(nlgn)\o(n \lg n) algorithm for constructing a binary search tree of nn elements. We can then use it to create a tree of nn elements and then use an inorder walk to gather the elements in an array in Ω(n)\Omega(n) time. This way we will produce an sorted array in o(nlgn)\o(n \lg n) worst-case time, which contradicts with the lower bound on comparison sort.