1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\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 '18 at 2:56
  • $\begingroup$ It showed up on my midterm and the answer was C actually... $\endgroup$ – Reyhaneh Rahimi Aug 17 '18 at 13:12
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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