(a) Consider the following function: def f(n): if n==0: return 0 elif n==1: return 1 else: val =6f(n1) val = val 9f(n2) return val 2 (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-O) 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 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-O) on the solution to this recurrence