(a) Consider the following function: deff(n) : if n=0 : return 0 elif n=1: return 1 else: val =6f(n1) val = val - 9f(n2) return val (i) Write a recurrence relation for the value returned by f. Solve the recurrence exactly. Don't forget to check it. (ii) Write a recurrence relation for the running time of f. Get a tight upperbound (big-0) on the solution to this recurrence. (b) Consider the following function: def f(n) : if n==0 : return 0 elif n==1 : return 1 else: val =4f(n1) val = val 4f(n2) return yal 6 (i) Write a recurrence relation for the value returned by f. Solve the recurrence exactly. Don't forget to check it. (ii) Write a recurrence relation for the running time of f. Get a tight upperbound (big-0) on the solution to this recurrence