4. Consider the following function: int f (int n){ if (n==0) return 2; else if (n==1) return 5; else{ int val 2*f (n-1); val = val - f (n-2); return val; } } (a) Write a recurrence relation for the value returned by f. Solve the recurrence exactly. (Don't forget to check it) (b) Write a recurrence relation for the running time of f. Get a tight upperbound (i.e. big-O) on the solution to this recurrence. 2