Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.