Problem 1: Assume that c ≥ 0, and assume you had some kind of super-hardware that, when given two lists of length n that are sorted, merges them into one sorted list, and takes only n c steps.
(a) Write down a recursive algorithm that uses this hardware to sort lists of length n.
(b) Write down a recurrence to describe the run time.
(c) For what values of c does this algorithm perform substantially better than O(n log n)? Why is it highly implausible that this kind of super-hardware could exist for these values of c?
Problem 2: In a binary tree, a leaf node is a node whose left and right children are both nil. The depth of the tree is the maximum number of edges between the root node and any leaf node.
Show that if a binary tree has depth n, then it has at most 2n leaf nodes.