Below you should answer questions about the recursion tree for the recursive function shown below for calculating Fibonacci numbers:

fib(n):

If n = 1 or 2, return 1

Otherwise, return fib(n-1) + fib(n-2)

1. How many nodes in the tree calculate fib(n)? How about for fib(n-1)? fib(n-2)? fib(n-3)? Answer all. (i.e. how many times has f(n-1) , f(n-2) been called etc.)

2. Now estimate the complexity of the fib function. If you do not see a pattern in #1, to help you try counting how many times n-4 and n-5 appear. You can express your answer as a summation