Help with the computer science question below

3. (12 marks] Recurrences. Consider the following algorithm that returns the k-th smallest element in an input array A. You may assume that all the elements in A are distinct. SELECT(A[1...n], k) if n p in A; if len(B) > k then | return SELECT(B,k); else | return SELECT(C, k len(B)); end end (a) [0 marks, optional] Convince yourself the correctness of the above algorithm. You don't need to hand in this part. (b) [6 marks] Write down the recurrence for the running time of the above recursive algo- rithm, and explain why it is correct. Hint: use the fact that M is an array of medians to bound the size of B and C. Remark: If you encounter some term in the form of T([an] + c) with constant a and c then you can ignore the ceiling (similar to floor) and constant c, and write T(an) for simplicity. (c) [4 marks) Based on the recurrence in part (b), use the recursion tree method to guess the correct order of the running time of SELECT(A[1...n), k). (d) [2 marks] Prove your guess in part (c) satisfies the recurrence in part (b) via induction. (e) [0 marks, optional] What is the running time of SELECT if we divide A into [] consec- utive subgroups of size at most 5? You don't need to hand in this part. 3. (12 marks] Recurrences. Consider the following algorithm that returns the k-th smallest element in an input array A. You may assume that all the elements in A are distinct. SELECT(A[1...n], k) if n p in A; if len(B) > k then | return SELECT(B,k); else | return SELECT(C, k len(B)); end end (a) [0 marks, optional] Convince yourself the correctness of the above algorithm. You don't need to hand in this part. (b) [6 marks] Write down the recurrence for the running time of the above recursive algo- rithm, and explain why it is correct. Hint: use the fact that M is an array of medians to bound the size of B and C. Remark: If you encounter some term in the form of T([an] + c) with constant a and c then you can ignore the ceiling (similar to floor) and constant c, and write T(an) for simplicity. (c) [4 marks) Based on the recurrence in part (b), use the recursion tree method to guess the correct order of the running time of SELECT(A[1...n), k). (d) [2 marks] Prove your guess in part (c) satisfies the recurrence in part (b) via induction. (e) [0 marks, optional] What is the running time of SELECT if we divide A into [] consec- utive subgroups of size at most 5? You don't need to hand in this part