2
$\begingroup$

I tried it as follows and would like to know if it is correct.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – David Richerby Mar 1 '15 at 0:17
  • $\begingroup$ @DavidRicherby Well then try not looking at my answer and answer it, if you can. I loved this site until everybody started finding faults of the questions asked rather than helping the one with the question. $\endgroup$ – S.Dan Mar 1 '15 at 0:21
  • 2
    $\begingroup$ From what I think you are trying to ask, yes $T(n)$ would be in $O(2^n)$ but you'd have a tighter upper bound with $T(n) \in O(\phi^n)$ where $\phi = \frac{1+\sqrt{5}}{2}$ $\endgroup$ – Francesco Gramano Mar 1 '15 at 2:31
  • 1
    $\begingroup$ Also, using images alone is not good style here. Please transcripe the text elements -- note that you can use LaTeX here (via MathJax). $\endgroup$ – Raphael Mar 1 '15 at 12:48
  • 2
    $\begingroup$ Your query is not even wrong. The "time complexity of the Fibonacci sequence" is not a thing. There are two meaningful things to ask here: 1) What is the asymptotic growth of the Fibonacci sequence (in $\Theta$)? 2) What is the asymptotic runtime of this algorithm computing the Fibonacci numbers? -- I guess you meant 2). For that, we have a couple of reference questions, and also for solving recurrences. $\endgroup$ – Raphael Mar 1 '15 at 12:50
5
$\begingroup$

The analysis is not accurate although the result is correct. You could write it more accurately by replacing $=$ with $\le$

$T(n) \le c(1+2+..+2^{n-1})$ ( $\le$ since not all level have same number of children, consider the most right-handed path, n is decreasing by $2$ every step ).

Indeed a more careful analysis can get you a tighter bound as mentioned in the comment. The idea is, the time $T(n)$ is computed with $T(n-1) + T(n-2)$ the same way as the actual fibonacci $F(n)$, and since $F(n) = O(\phi^n)$ for $\phi = (1+\sqrt{5})/2$ as the closed form.

Thus $T(n) = O(\phi^n)$ which is slightly smaller than $2^n$

$\endgroup$
  • 1
    $\begingroup$ For the second part, one has to be mindful of the additional toll term $c$ in the recurrence of $T$. The recurrence for $F$ only counts leaves but the one of $T$ counts all nodes. It is not always the case that the number of leaves dominates asymptotically, cf. recursion tree method. $\endgroup$ – Raphael Mar 1 '15 at 12:53

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