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.

-

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.

-
Thanks @Gerry, I don't have experience handling this. –  leo Aug 24 '11 at 1:01
You're right @Gerry, in the comment below. This really answer my question. –  leo Aug 25 '11 at 21:19

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.

-
But is there a recursive algorithm whose running time is given by the recursion $a_{n+2}+a_n=0$? I read the problem as asking whether there could be an algorithm whose running time satisfied a recursion with complex roots. But maybe I was reading something into the question that wasn't there. –  Gerry Myerson Aug 24 '11 at 1:20
For $a_{n+2}+a_n=0$, certainly not. But we can certainly imagine an algorithm which behaves differently depending on the equivalence class of $n$ modulo $4$. So it is conceivable that we will end up with sines and cosines. But in general the explicit solution of a recurrence is not all that useful. But I wanted to show that explicit solutions are achievable using the general procedure the OP has been taught, even in the complex root case. –  André Nicolas Aug 24 '11 at 1:29
@André: I don't have problem with the general case. For any recurrence relation that I have to solve, I will be satisfied if I achieve a formula in terms of $n$ although involve complex numbers. But if the recurrence relation comes from an algorithm that perform a "real" task, I espect that in the running time function don't appear complex things. But, now that I think it, perhaps it is just a illusion. –  leo Aug 24 '11 at 2:54
You are probably right about complex numbers not appearing often. What I would expect is that when they do occur, it is in terms of the solution which grow much more slowly than the main term. So I would expect that for "big $O$" estimates they would be irrelevant. –  André Nicolas Aug 24 '11 at 3:07
For fun I checked the example given by @Gerry Myerson. The real root is about $1.84$, giving a contribution of a constant times $(1.84)^n$. Each non-real root has norm about $0.74$. So the contribution of the two combined non-real terms (which is very real!) is a constant times $(0.74)^n$ roughly. This contribution actually approaches $0$ as $n$ gets large, so it is really dwarfed by the $(1.84)^n$ term. That's probably what we would usually do with the non-real terms: look at them long enough to observe we don't need to worry about them. –  André Nicolas Aug 24 '11 at 3:18