In class we did different cases of Quicksort algorithm for various splits of the input data based on a choice of the pivot. For this problem we are going to assume that a pivot is selected such that data is partitioned in the ratio of 2 to 1 every time. The partition routine would remain the same as used in class and so would the number of comparisons in it. Answer the following questions: (a) Write the recurrence equation, and the base case.
(b) What is the height of the recursion tree?
(c) Solve the recurrence equation using an appropriate method. Justify your method
(d) Verify the base case.