Analysis of algorithms and recurrence relations Suppose that the function of the time of execution of some recursive algorithm is given by a recurrence relation of order $n$. Let $$p(x)=0,$$ with $p(x)$ a polynomial of degree $n$, the corresponding characteristic equation of the recurrence relation. I want to know, if it is possible that $p(x)$ has complex roots. If not, does there exist some theorem that sustain this? If yes, what is a example?
Thanks.
 A: There is no particular theoretical problem with complex roots of characteristic polynomials.  But if we want to avoid explicit mention of powers of a non-real number, there is some extra work to do.
The (almost) simplest example is $a_{n+2}+a_n=0$, with say $a_0=1$ and $a_1=-1$.
The roots of the characteristic polynomial are $i$ and $-i$.  So the general solution is $Ai^n+B(-i)^n$. To find $A$ and $B$, use the initial conditions.
From the value of $a_0$, we find that $A+B=1$.  From the value of $a_1$, we find that $Ai-Bi=-1$, or equivalently $A-B=i$.
Solve. We obtain $A=(1+i)/2$ and $B=(1-i)/2$.
So the solution to our recurrence is given by
$$a_n=\frac{1+i}{2}i^n +\frac{1-i}{2}(-i)^n.$$
This is correct, but not entirely satisfying!  So let's simplify.
Note that $i^n=1$ if $n \equiv 0 \pmod{4}$, $i^n=i$ if $n \equiv 1 \pmod{4}$, $i^n=-1$ if $n \equiv 2\pmod 4$, and $i^n=-i$ if $n\equiv 3\pmod{4}$.
Compute. When $n\equiv 0\pmod 4$, we get $a_n=1$. When $n \equiv 1 \pmod {4}$, we get $a_n=-1$, and in the other two cases we get $a_n=-1$ and $a_n=1$ respectively.
There are of course more complicated situations.  If our root is $a+bi$, it may be useful to express $(a+bi)^n$ in polar form.  There is a number $\theta$ such that $a+bi=c(\cos\theta+i\sin\theta)$, where $c=\sqrt{a^2+b^2}$. Then $(a+bi)^n=c^n(\cos n\theta +i\sin n\theta)$. If the $a_n$ are real, we may wish to express $a_n$ using powers of a real number and sines and cosines.
The complex solutions of the characteristic equation will come in complex conjugate pairs.  It turns out that we can use $\cos\theta=(e^{i\theta}+e^{-i\theta})/2$ and  $\sin\theta=(e^{i\theta}-e^{-i\theta})/2i$ to get rid of all mention of $i$ in the expression for $a_n$, if we so wish.   
Added:  What does this have to do with analysis of algorithms? In general, probably not much. I would expect that most of the time, the roots of the characteristic equation will be real. 
Even when not all the solutions are real, I would expect that the "norms" of the non-real roots will be smaller than the norm of at least one real root.  (The norm of $a+bi$ is $\sqrt{a^2+b^2}$.) 
What this means practically is that the contribution of the non-real roots to the size of $a_n$ is, for large $n$, negligible in comparison with the contribution of the largest real root.
A: Let $a_n$ be the number of $n$-symbol words on the alphabet $\lbrace r,ss,ttt\rbrace$. Then $a_n$ satisfies a recurrence with characteristic equation $x^3-x^2-x-1=0$, which has (two) complex roots (and one real root). 
For an algorithm, consider computing $a_n$ by computing $a_{n-1},a_{n-2},a_{n-3}$ and adding. 
