Consider this recursive function: int foo(int N) { if (N = res 2) return res1; else return res2; } a) Write the recurrence formula for

Consider this recursive function:

int foo(int N)

{ if (N <= 1) return 5;

int res1 = 3*foo(N/2);

int res2 = foo(N-1);

if (res1 >= res 2) return res1;

else return res2;

}

a) Write the recurrence formula for the TIME COMPLEXITY of this function, including the base cases for N>=0. You do NOT need to solve the recurrence. Remember not to confuse the time complexity of the function with what the function calculates.

b) Draw the tree that shows the function calls performed in order to compute foo(5) (the root will be foo(5) and it will have a child for each recursive call.) Also show what each call returns by using an arrow pointing back from the child to the parent. 4 In a file called foo.c implement the following functions:

c) int foo_iterative (int N) - ITERATIVE solution of this code.

d) foo_memoized(. ) - the MEMOIZED solution. The function signature can be whatever you want.MUST PRINT THE RECURSIVE and BASE CASE CALLS.

They should show the N that the function was called for and the text should be indented based on the depth. See for a sample print with indentation based on the depth (min_rec_2_rec_calls_tree.txt ) and the code that does that (print_rec_call.txt).

e) int foo_wrapper(int N) - a wrapper function that calls the foo_memoized.

program should in C code