Consider any comparison-based sorting algorithm on A[1 to n].

(30 pts) Consider any comparison-based sorting algorithm on Al1 to n]. It creates a decision tree T as discussed in class, each internal node of which decides whether AlijS A[i] for some specific elements Ali] and A[i']. Its leaf determines an order of Al1 to n] completely. Answer the five questions regarding T 3. A) (6pts) How many leaves does T have? Justify your answer in 1-3 lines. B) (6pts) Find the tightest asymptotic lower bound on the depth of T with the big 2-notation. Justify your answer in 1-5 lines. (6pts) Prove in 1-5 lines that the worst-case number of comparisons equals the depth of T. (6pts) Prove in 1-5 lines that any comparison-based sorting algorithm takes at least C) D) l(n log n) time to sort A[1 to nj E) (6pts) Consider the bucket sort algorithm: it checks the value of each Alij, and if Alij-i, store it in the ith bucket out of m. Then sort A[1 to n] in the order of buckets 1, 2,., m. Explain in 1-8 lines why bucket sort runs in O(n+m) time and why it can run faster than L(n log n) time despite D