The function fib implemented the recurrence Fn. We can characterize the time taken by fib in terms of the number of additions (plusses) performed. We can write a recurrence TF(n) that computes this number as follows. Observe that there are no additions performed for the base cases. Hence Tf(0) = 0 and Tf(1) = 0. Also observe that the number of additions to compute Fn is one more than the number of additions to compute Fn-1 together with the number of additions to compute Fn-2. Hence TF(n) = 1 +Tf(n 1) + Tf(n 2). Putting this together, we have the following recurrence. = 0 TF(0) TF(1) Tf(n) = 0 1+TF(n 1) + TF(n 2) = It turns out that for any n E N, TF(n) = Fn+1 1. Use limits together with theorem 3 to show that TF(n) e O(6")