Suppose we want to design a binary decision tree of comparisons that can determine the sorted order of any input list of 4 distinct positive integers a_1, a_2, a_3, a_4 in that order. For example, the input might be a_1 = 7, a_2 = 3, a_3 = 6, a_4 = 5. So, the first integer is denoted a_1, and so on. At each node in the tree, we compare the values of two specific entries a_i, a_j in the list, then descend to a child node according to the result of the comparison at the parent node. Each leaf should correspond to a specific sorted order of the entries, for example a_3 a_1 a_2 a_4. a. How many leaves should the binary tree have, in order to accommodate all possible sorted orders? Explain in terms of this specific example with 4 input items. b. What must be the height of the binary tree in order to provide enough leaves? Explain in terms of this specific example with 4 input items. c. Is the height you gave above in b. a lower bound or an upper bound for the height of any binary decision tree you might design to determine the sorted order of the 4 input items? d. Using asymptotic notation, what must the height, h, of the tree be in order to sort n items? Prove it. You may assume the general case corresponding to parts a. and b. are true