# Finding the time complexity of fibonacci sequence [closed]

I tried it as follows and would like to know if it is correct. • @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. Mar 1, 2015 at 0:21
• 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}$ Mar 1, 2015 at 2:31
• Also, using images alone is not good style here. Please transcripe the text elements -- note that you can use LaTeX here (via MathJax).
– Raphael
Mar 1, 2015 at 12:48
• 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.
– Raphael
Mar 1, 2015 at 12:50

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