Please show all steps in detail on how to solve the problem.

10. The following divide-and-conquer algorithm is designed to return TRUE if and only if all elements of the array have equal values. For simplicity, suppose the array size is n = 2k for some integer k. Input S is the starting index, and n is the number of elements starting at S. The initial call is SAME(A, 0,n). Boolean SAME int A, int S, int n) Boolean T1,T2, T3 if (n == 1) return TRUE; T1 = SAME (A,S, n/2); T2 = SAME (A, S + n/2, n/2); return (TI AT2 AT3) (a) Explain how this program works (b) Prove by induction that the algorithm returns TRUE if and only if all elements of the array have equal values f(n) be the number of key comparisons in this recurrence for f(n (c) Let algorithm for an array of size n. Write a (d) Find the solution by repeated substitution