Analysis of algorithms and recurrence relations

Question

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.

Answer 1

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.

Answer 2

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.