(Answered): Problem 4: A divide and conquer MAXMIN algorithm is presented as a pseudo-code below. procedure MAX ...

Problem 4: A divide and conquer MAXMIN algorithm is presented as a pseudo-code below. procedure MAXMIN input: (A1... ) of numbers) output: (min,max) begin if (n = 1) return (A1), A21) else if ( 12) if (All < A(21) return (A1), A(21) else return (A2), A[1]) else (min.left, max_left) - MAXMIN(A1-(1/2)]) (min.right,max-right)-MAXMIN(A|(n/2+1)... 1]) if (max left<max right) max=max_right else max=max_left if (min-left<min-right) min-min left else mnin-min_right return (min, max) end For simplicity, assume that n is a power of 2. (a) Analyze the pseudo-code, and give the recurrence T(12) for the number of comparisons performed by the maxmin procedure. (b) Prove (by induction!!!) that T(n) = 1 - 2 for all n which are powers of 2.