I tried it as follows and would like to know if it is correct.
$\begingroup$
$\endgroup$
7
-
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 RicherbyCommented Mar 1, 2015 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.DanCommented Mar 1, 2015 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 GramanoCommented Mar 1, 2015 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$– RaphaelCommented Mar 1, 2015 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$– RaphaelCommented Mar 1, 2015 at 12:50
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
1
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$
-
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$– RaphaelCommented Mar 1, 2015 at 12:53