2
$\begingroup$

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

enter image description here

$\endgroup$

closed as unclear what you're asking by David Richerby, Luke Mathieson, Guildenstern, Wandering Logic, Juho Mar 1 '15 at 17:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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