Data Structures Question

Example Problem with solution (do not provide a solution as it is already solved):

1. For the pseudo-code below, give the recurrence relation expressing the worst case run time when foo(A,n) is called (.e., expressT( Assume that the function bar (n) costs cn on an input of size n. Show your work, next to each line in the pseudo code write the total cost for that line. I want to understand how you obtained the recurrence. (Note: It doesn't matter what the algorithm does. Do not spend time trying to under stand the code, just evaluate the running time.) foo(A, n) takes as an input the array A with n elements, n>-1 if (n