Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
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
add comment

4 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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