Only answer #4. I finished #3.

(1 point) 3. Let t1 = a + (b-a)/3] and t2 = b-f(b-a)/31 denote the indices at one third and two thirds the way from a to b, respectively. Let pairsort(X,Y) be a function that returns Y|X if X and Y are both odd and X Y, otherwise returns XY. Below is another self-reduction for the ODDSORT problem. State a recursive algorithm using pseudocode for solving the ODDSORT problem based on this self-reduction. pairsort(A[a], A[b]) if a b if b=a+1 if b> a+1 A SOS(Aa...b]) = with A' A" A" - - - SOS(Aa... t2] || At2 +1...b] A'[a... t] || SOS(A' (t1 +1...b]) SOS(A"[a...tz] || A"(t2 +1...b] (2+2 points) 4. Using the same reduction as in item 3 above, state a recurrence T'(n) that expresses the worst case running time of the recursive algorithm. From this recurrence, find a tight (Big-Theta) expression for T'(n). Hint: the Master Theorem may be the easiest solution (1 point) 3. Let t1 = a + (b-a)/3] and t2 = b-f(b-a)/31 denote the indices at one third and two thirds the way from a to b, respectively. Let pairsort(X,Y) be a function that returns Y|X if X and Y are both odd and X Y, otherwise returns XY. Below is another self-reduction for the ODDSORT problem. State a recursive algorithm using pseudocode for solving the ODDSORT problem based on this self-reduction. pairsort(A[a], A[b]) if a b if b=a+1 if b> a+1 A SOS(Aa...b]) = with A' A" A" - - - SOS(Aa... t2] || At2 +1...b] A'[a... t] || SOS(A' (t1 +1...b]) SOS(A"[a...tz] || A"(t2 +1...b] (2+2 points) 4. Using the same reduction as in item 3 above, state a recurrence T'(n) that expresses the worst case running time of the recursive algorithm. From this recurrence, find a tight (Big-Theta) expression for T'(n). Hint: the Master Theorem may be the easiest solution