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.