Asymptotic bound of a recursive function

Question

Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N?

F(i):
 if i<3then
 return 0 
 end if
 return F(i−1) + F(i−2)

$• A. O(N) • B. O(N^2) • C.O(2^N) • D. O(N log(N))$

---

This may seem like a dumb question but I have no idea how to get asymptotic bounds for recursive methods. I got the following recurrence relation: $T(n)=T(n-1)+T(n-2)$ but I'm not sure where to go from here. The answer is supposed to be C.

• 喜欢算法和数学: F(1)=0. F(2)=0. F(3)=F(2)+F(1)=0. ....So F(i) = 0 for all i >=0. So the best answer is A.
• Reyhaneh Rahimi: It showed up on my midterm and the answer was C actually...

Answer 1

The recurrence relation $T(n) = T(n-1) + T(n-2),ドル with initial conditions $T(2) = T(1) = 1,ドル has as solution the Fibonacci numbers, whose asymptotic growth is known to be $\Theta(\phi^n),ドル where $\phi = \frac{1+\sqrt{5}}{2} < 2$. The same bound holds for arbitrary positive initial conditions.