Data Structures Question

Problem (needed solution)

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

4. (15 pts) For the pseudo-code below, give the recurrence relation expressing the worst case run time when foo(A,n) is called .e., express T(n)). Assume that the function bar (n) has complexity (n). Do not forget the base case Show your work, next to each line in the pseudo code write the number times it gets executed. I want to understand how you obtained the recurrence. You do not need to solve the recurrence Just derive it (Note: It doesn't matter what the algorithm does. Do not spend time trying to understand the code, just evaluate the running time foo(A, n) // takes as an input the array A with n elements, n>-1 if (n