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