Consider the following argument for proving that any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes (n log n) time in the worst case.

Let B be any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements. Let T(n) be its worst-case running time. Let S be the following comparison-based sorting algorithm (that uses B); input array is a[1..n].

Alg. S

Step 1. Call B to construct a BST T on the keys in a[1..n].

Step 2. Do an inorder traversal of T to print the keys in sorted order.

Note that the worst-case running time of S is T(n) + (n); By the ITLB for sorting we know that the worst-case running time of S must be (n log n), that is, T(n) + (n) = (n log n); consequently, T(n) = (n log n) (n) = (n log n), as required.

ANSWER FOLLOWING QUESTIONS

(a) Is the above argument correct? why or why not? If you think the argument is incorrect, can you revise it to a valid proof?

(b) Consider the design of an algorithm for printing out the keys of an n-node binary minheap in sorted order. Prove or disprove: this task can be accomplished in O(n) time.