(Solved): 1. In class we used the Blum-Floyd-Rivest-Pratt-Tarjan select algorithm to find the k-th smallest ...

1. In class we used the Blum-Floyd-Rivest-Pratt-Tarjan select algorithm to find the k-th smallest value using n/5 blocks of size 5, each. Assume for this problem, we are using n/3 blocks, each of size 3. (a) Find the number of comparisons for each step of the algorithm. (b) Obtain the overall recurrence equation for the upper bound on the number of comparisons and solve it. (e) What are your observations about the difference in the asymptotic runtime between a block of size 3 vs. 5 (the one we did in class)? Explain the reason for those differences briefly.