1. (a) Suppose that the splits at every level of quicksort are in the constant proportion a to ẞ, where a + B = 1 and 0 < a < ß < 1. Show that the minimum depth of a leaf in the recursion tree is approximately log₁/an and the maximum depth is approximately log 1/8 n. (Do not worry about integer roundoff.) log1/ẞ (b) Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(an) +T(ẞn) + cn, where c > 0 is a constant. 2. Consider performing Quicksort on an array with n elements, where each element has either value a or value b. Assume there are na elements with value a and nɩ elements with value b; so n = na +n. Explain what the subarrays look like after the Partition step and use this to write out a recurrence for the left subarray and a recurrence for the right subarray. Solve the two recurrences to obtain the running time of Quicksort for this case.

1. (a) Suppose that the splits at every level of quicksort are in the constant proportion a to ẞ, where a + B = 1 and 0 < a < ß < 1. Show that the minimum depth of a leaf in the recursion tree is approximately log₁/an and the maximum depth is approximately log 1/8 n. (Do not worry about integer roundoff.) log1/ẞ (b) Use a recursion tree to give an asymptotically tight solution to the recurrence T(n) = T(an) +T(ẞn) + cn, where c > 0 is a constant. 2. Consider performing Quicksort on an array with n elements, where each element has either value a or value b. Assume there are na elements with value a and nɩ elements with value b; so n = na +n. Explain what the subarrays look like after the Partition step and use this to write out a recurrence for the left subarray and a recurrence for the right subarray. Solve the two recurrences to obtain the running time of Quicksort for this case.