Consider this recursive function foo(N): int foo(int N){ if (N <= 1) return 5; return foo(N-2) * foo(N-2); } Use the function definition as is. There is no error. a) (3 points) Write the recurrence formula for this function. b) (3 points) Solve the recurrence formula you gave above to compute the bigO complexity of this function. c) (6 points) Draw the tree that shows the function calls performed in order to compute foo(7) (the root will be foo(7) and it will have a child for each recursive call.) 3 d) (6 points) Use the tree to compute the number of function calls as a function of N (not the specific number of recursive function calls for foo(7), but a formula that would give the number of calls for any N. SHOW YOUR WORK. (Continue on the next page if needed) e) (6 points) Is it possible to re-implement this function so that it has running time O(N)? If not, why not? If yes, write this O(N) implementation of foo in C.