gotchaModerate
Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
Viewed 0 times
whyfracomegarecurrenceyielddoessomething
Problem
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?
Why does this algorithm have a time complexity of $\Omega(2^{\frac{n}{2}})$? Where does the exponent come from?
Solution
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| 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.
$$ 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| 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.
Context
StackExchange Computer Science Q#9899, answer score: 14
Revisions (0)
No revisions yet.