2. (U & G-required) [40 points]

(a) [20 points] Implement in C/C++ a divide and conquer algorithm for finding the position of the largest element in an array of n numbers. Show how your algorithm runs on the input A = [1 4 9 3 4 9 5 6 9 3 7].

(b) [10 points] What will be your algorithms output for arrays with several elements of the largest value? Indicate the answer on the input given above.

(c) [10 points] Set up and solve a recurrence relation for the number of key comparisons made by your algorithm.