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

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; } 

1* Write the recurrence formula for the TIME COMPLEXITY of this function, including the base cases for N>=0. (You do NOT need to solve it.) (Note that it should NOT be the formula for what the function computes, but for how long it takes.)

2* 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.

3* Write the memoized version of this function in a file called memoization.c. 4* Re-implement this function with memoization (i.e. use a solution array to look-up and store results of recursive calls). The function signature can be whatever you want. 5* Write a wrapper function that calls the memoized foo function. The signature should be: int foo_wrapper(int N) . 6* The main function should call and print the result for foo_wrapper(15) and then for foo_wrapper(10) and after that it should repeatedly read N from the user and call foo_wrapper(N) and print the result until the user enters -1 for N.