2. (10 points) Consider the following recursive codes. For each, write the recurrences that expresses its worst-case run time T(n). Show your work along the code lines, i.e. I want to understand how you derive the recurrence. On the page with the code, next to each line of code give the total cost when the algorithm gets executed, be careful how do you account for the recursive calls, and then at the bottom give the recurrence. Do not forget the base case. It does not matter what the algorithms do, just derive the recurrences. You do not have to solve the recurrences and do not have to tell me what the asymptotic time complexity is. Code 1 bar(A,p,r) { // A[p..r) is an array of size n= r - p+1 if r == p return A[p] q = (p+r)/2 a = bar (A,p, q) // A[p..q] is left half of A[p..r] b = bar(A, 2+1,r) // A [q+1..r] is the right half of A[p..r] return a + b Code 2 foo(A, B, C, n) { // process arrays A[1..n], B[1..n), and C[1..n] if n == 1 print * return foo(A, C, B, n-1) // process arrays A[1..n-1), C[1..n-1)], and B[1.., n-1] foo(B, C , A , n-1) // process arrays B[1..n-1), C[1..n-1), and A[1..n-1] print *