4. Divide and conquer, and the Master Theorem. For each of the following recursive algorithms, give (with brief justification) a recurrence for the algorithm's running time T(n) as a function of the input array size n. State whether the Master Theorem is applicable to the recurrence, and if so, use it to give the closed-form solution; if not, explain why not. (a) (b) 1: function FUNC(A[1,..., n]) if n A[n] then swap A[1] and A[n] if n > 2 then t [2n/3] STOOGESORT (A[1,, t]) STOOGESORT (A[n t + 1, . . ., n]) STOOGESORT (A[1,..., t]) - return A Solution: (d) Optional extra credit: Prove that STOOGESORT from the previous part is a correct sorting algorithm. Solution: