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?

    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.

  • $\begingroup$ 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. $\endgroup$
    – John L.
    Aug 17, 2018 at 2:56
  • $\begingroup$ It showed up on my midterm and the answer was C actually... $\endgroup$ Aug 17, 2018 at 13:12

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.