# Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).

Why does this algorithm have a time complexity of $\Omega(2^{\frac{n}{2}})$? Where does the exponent come from?

-
Try writing a recurrence relation expressing the running time and solve it. –  saadtaame Feb 18 '13 at 19:20
Just to be clear, "time complexity of at least" is talking about the lower bound. Here it means that the lower bound is of $O(2^{n/2})$, which basically means that $T(n) \in \Omega(2^{n/2})$. The answers below demonstrate this fact. –  Paresh Feb 18 '13 at 21:37
"the lower bound is of $O(\\_)$" resp "at least $O(\\_)$" -- that does not make much sense. The lower bound needs to be in $\Omega(\\_)$, too. See also here. –  Raphael Feb 19 '13 at 6:15
@Raphael Oh I agree it is an abuse of the notation, and should not be used, but unfortunately I have seen it being used. When saying $f(n)$ is atleast $O(g(n))$, what is being implied (and hence the abuse) is that $g(n)$ is a tight upper bound on some $h(n)$, and that $f(n)$ is $\Omega(h(n))$, thereby also implying $f(n) \in \Omega(g(n))$. –  Paresh Feb 19 '13 at 7:54
@Raphael But yeah, your edit of the question seems the right way to go. –  Paresh Feb 19 '13 at 8:34

Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form $$T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n,$$ for some $A,B$. Note that $|(1-\sqrt{5})/2| < 1$, and so the second term tends to zero as $n \longrightarrow \infty$. Assuming that $T(n)$ tends to infinity, $A > 0$ and so $$T(n) = \Theta\left( \left( \frac{1+\sqrt{5}}{2} \right)^n \right).$$ Now $(1+\sqrt{5})/2 > \sqrt{2}$, and so $T(n) = \Omega(2^{n/2})$.

Edit: This part is also covered in this answer (see under "A Shortcut").

More generally, for a recurrence of the form $T(n) = \sum_{i=1}^k a_i T(n-i)$, let $$P(t) = t^n - \sum_{i=1}^k a_i t^{n-i}.$$ If $P$ has no repeated roots and the (possibly complex) roots are $\lambda_1,\ldots,\lambda_k$, then the solution is always of the form $$T(n) = \sum_{i=1}^k A_i \lambda_i^n.$$ If it does have repeated roots, say the roots are $\lambda_1,\ldots,\lambda_l$ with multiplicities $m_1,\ldots,m_l$, then the solution is always of the form $$T(n) = \sum_{i=1}^l A_i(n) \lambda_i^n,$$ where $A_i$ is a (possibly complex) polynomial of degree smaller than $m_i$.

In our case, $P(t) = t^2-t-1$ has no repeated roots, and the two roots are $(1\pm\sqrt{5})/2$.

The $A_i$s depend on the initial values, and can be found by solving linear equations. For example, suppose we are given $T(0)$ and $T(1)$ for our recurrence. Then we can find $A,B$ by solving the system \begin{align*} T(0) &= A + B, \\ T(1) &= \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B. \end{align*} This works even in the case of repeated roots, and $k$ initial values always suffice. Assuming $a_k \neq 0$, $k$ initial values are also necessary.

-
I think the second part of your answer has been covered here ("A Shortcut"). If not, you should probably add an answer there with the general idea. –  Raphael Feb 19 '13 at 6:17
Thanks for the link, it is indeed covered there. –  Yuval Filmus Feb 19 '13 at 6:48

It's not $O(2^{n\over 2})$ is $\Theta(\phi^n)$ which doesn't belong to $O(2^{n\over 2})$ but you can say belongs to $\Omega(2^{n\over 2})$ or belongs to $O(2^n)$ (and saadtaame showed this in his answer), So be careful about abuse of notations. But why is $\Theta(\phi^n)$? as a student of CS you should try to solve it yourself but if you tried and you couldn't show it, show us your try and we can help you.

Oh Seems I forgot to say why is in $\Omega(2^{n\over 2})$ (and I think your main question was this, or totally you were wrong): $T(n) = T(n-1)+T(n-2) \gt 2T(n-2)$ and this results: $T(n) > 2^{n\over 2}T(0)$.

-

The running time of the naive solution is: $$T(n)=T(n-1)+T(n-2) \lt 2T(n-1)$$ Now, $$2T(n-1)=2(2T(n-2))=2(2(2T(n-3)))=\dots=2^kT(n-k)=\dots=2^nT(0)=O(2^n)$$

The base case takes time $T(0)=\Theta(1)$. So that's where the exponent is coming from. This result is an upper bound; you can obtain a tighter bound if you solve the recurrence using generating functions for example.

-
Again, $O(2^n)$ is not the end result we need; we need $\Omega$. –  Raphael Feb 19 '13 at 6:18
This can be 'flipped around' to give the result the OP is after, though - I'll write it up in a moment here. –  Steven Stadnicki Feb 19 '13 at 23:44

you can find for Every linear recurrence with constant coefficients a closed form. (See the link) the Fibonacci numbers have a closed-form solution as (the approximation is for large ns):

$F_n \times \sqrt{5} ={ \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) }^{ n }-{ \left( \frac { 1-\sqrt { 5 } }{ 2 } \right) }^{ n } \simeq { \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) }^{ n } \simeq (1.6180..)^n \simeq 2.89^{n/2}$

or more formaly $F_n \in\Omega (2^{n/2})$.

You can find more in Conceret Mathematics, by Ronald L. Graham, Donald E. Knuth and Oren Patashnik, chapter 6 : Special Numbers.

-
That's not helping. You are confusing the OP. –  saadtaame Feb 18 '13 at 19:52
@saadtaame: This is the exact way of computing Fibonacci or any constant coefficient recursive relation. It could be found in any cobinatorial book, no confusion at all !. I think this is nessasary for any computer science student to know. –  Reza Feb 18 '13 at 19:58
What does "is at least $O(2^{n/2})$" mean? please use mathematical definitions and validate your sentence with big-oh definition. –  user742 Feb 18 '13 at 20:06
"at least $O(\dots)$" not a meaningful statement, as $1 \in O(f)$ for most functions $f$ that pop up in algorithm analysis. –  Raphael Feb 19 '13 at 6:20