Data Structures, Algorithms, & Applications in C++
Chapter 14, Exercise 11

(a)

We can sort elements using the steps (1) initialize a binary search tree with the elements to be sorted and (2) output the elements in sorted order using the inorder method. The time required to sort n elements using these two steps is O(time to initialize the tree + n) = O(time to initialize the tree). Therefore, the asymptotic complexity of the two step sort method is the same as that to initialize an n element binary search tree. Since there can be no sort algorithm whose complexity is less than O(n log n), there is no algorithm that initializes an n element binary search tree and takes less than O(n log n) time.

(b)

We construct the following sort algorithm (1) create n binary search trees, each containing one of the elements to be sorted; (2) perform ceil(log2n) rounds of combining pairs of binary search trees, in round one n/2 pairs of trees of size one are combined to obtain trees of size two, in round two n/4 pairs of trees of size at most two are combined to obtain trees of size four, and so on; (3) output, in inorder, the elements of the single size n element tree that remains.

Let t(a+b) be the time taken to combine two binary search trees of size a and b respectively. The time taken by step (2) is at most nt(2)/2 + nt(4)/4 + nt(8)/8 + .... This time is less than O(n log n) when t(a+b) < O(a+b). Therefore, when t(a+b) < O(a+b), the total sort time is less than O(n log n) (note that steps (1) and (3) take O(n) time each). Since it is not possible to sort in less than O(n log n) time, the time to combine two binary search trees of size a and b respectively must be at least O(a+b).