Answer the following questions on recurrences: (a) [3 pts] Write a recurrence for the running time T(n) of f(n), and solve that recurrence. Assume tha.t addition can be done in constant time. Express your final answer in -notiation. def f(n): if n==1: return 1 else : return f(n1)+f(n1) (b) [3 pts] Write a recurrence for the running time of g(n), and solve that recurrence. Assume that addition can be done in constant time. Express your final answer in -notation. def g(n): if n==1: return 1 else : x=g(n1) return x+x (c) [4 pts] Now assume addition takes time (b), where b is the number of bits in the larger number. Write a new recurrence for the running time of g(n), and solve that recurrence. Express your final answer in -notation