The recurrence relation for the number of comparisons in Selection Sort is: C(n) = 0 n = 1 (n - 1) + C(n - 1) otherwise a.) Solve the recurrence relation. b.) Prove that your solution is correct. The recurrence relation for the number of comparisons in Merge Sort is: C (n) = 0 n = 1 2C(n/2) + n - 1 Otherwise a.) Solve the recurrence relation. b.) Prove that your solution is correct. (a) Write a Divide & Conquer recursive procedure DINDEX to find index of the largest element in an array of n elements. (b)Calculate the number of comparisons C(n) by solving recurrence relation in (a) and prove your result. Solve and prove your solution for following recurrence relation for Binary Search: C(2^1 - 1) = 1 C(2^i - 1) = 2 + C(2^i-1 - 1) a.) Solve the recurrence relation. b.) Prove that your solution is correct