(a) (Nothing to prove here) Suppose that p is the (k+1)-th smallest element in A, so that the pivot appears in B at B[k]. In this case, the length of Ao is k and the length of A₁ is n - k- 1, and so the expected runtime of the recursive calls made in Step 4 is Tk + Tn-k-1. Because the pivot was chosen randomly, the probability that p is indeed the (k+1)-th smallest element in A is 1/n for all k = 0,..., n - 1. Therefore, the expected runtime of the recursive calls is 1/2 h=(Tk + Tn-k-1). Finally, choosing the pivot takes time O(1) and the filter step takes time O(n). Thus, Tr satisfies: nk=0 n-1 1 Tn = cn +=(Tk + Tn_k_1). k=0 This will be our starting point. Also, note T₁ = 1. (b) Prove n Tn = cn² +2=Tk. (c) Deduce n. Tn = c(2n-1) + (n +1) · Tn-1. (d) Deduce n Tn n+1 2c n+1 + Tn-1, n (e) Now iterate this bound to get 1 ≤2c(+1+ + ... + 1/3 ) + 1/2 . n+1 n (f) Finally use the fact from calculus: 1+ ½ + 3 + ··· +/= O(log n) to get In = O(n log n).

(a) (Nothing to prove here) Suppose that p is the (k+1)-th smallest element in A, so that the pivot appears in B at B[k]. In this case, the length of Ao is k and the length of A₁ is n - k- 1, and so the expected runtime of the recursive calls made in Step 4 is Tk + Tn-k-1. Because the pivot was chosen randomly, the probability that p is indeed the (k+1)-th smallest element in A is 1/n for all k = 0,..., n - 1. Therefore, the expected runtime of the recursive calls is 1/2 h=(Tk + Tn-k-1). Finally, choosing the pivot takes time O(1) and the filter step takes time O(n). Thus, Tr satisfies: nk=0 n-1 1 Tn = cn +=(Tk + Tn_k_1). k=0 This will be our starting point. Also, note T₁ = 1. (b) Prove n Tn = cn² +2=Tk. (c) Deduce n. Tn = c(2n-1) + (n +1) · Tn-1. (d) Deduce n Tn n+1 2c n+1 + Tn-1, n (e) Now iterate this bound to get 1 ≤2c(+1+ + ... + 1/3 ) + 1/2 . n+1 n (f) Finally use the fact from calculus: 1+ ½ + 3 + ··· +/= O(log n) to get In = O(n log n).