PROBLEM 1 Why 5 in Median? Recall the deterministic selection algorithm: 1: procedure SELECT(A[1,.. . ,n],i)) 3: if n Recursion r-11-MoM and MoM Recursion return SELECT(A1,.. . ,r-1],i) end if 18 D Recursion end if 21: end procedure 20: (a) In class, we showed that with k 5, the value of r returned by PARTITION(A1, , nj, MoM) is at least 3n/10- 3/2 and at most 7n/10+5/2. Suppose that instead we use k- 3. State an upper and lower bound on the value of r returned by PARTITION(..,n], MoM). Be as precise as you can. Solution: (b) Write a recurrence for S(n), the running time of SELECT(A[1,...,n],i), using the bounds on r you got for k-3 Solution: (c) Use induction to prove S(n) (n log n) for k-3. Ignore all ceiling/ floor for simplicity Solution