9
$\begingroup$

In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.

Say I have concluded that a characteristic polynomial $x^2 - 2x + 2$ has imaginary roots, namely $x_1 = 1+i$ and $x_2 =1-i$. Then I cannot use

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

to obtain the solution, right? How should I proceed in this case?

$\endgroup$
  • $\begingroup$ Welcome! Note that you can use LaTeX by $...$. $\endgroup$ – Raphael Mar 31 '12 at 10:38
  • 1
    $\begingroup$ I am confused. I am sure you mean the method using characteristc polynomials, not equations. What is $j$? The solutions of the equation you give are not imaginary, but merely irrational. What do you mean by "apply the [polynomial]"? $\endgroup$ – Raphael Mar 31 '12 at 10:40
  • 6
    $\begingroup$ He's adopted the physicist's habit of misspelling $i$. $\endgroup$ – JeffE Mar 31 '12 at 11:41
  • $\begingroup$ Of course, you can actually. First, the solution satisfies the reoccurrence. Second, the solution space is of dimension 2. $\endgroup$ – Strin Apr 3 '12 at 5:23
12
$\begingroup$

Yes, the solution is in fact $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$ determined by the base cases. If the bases cases are real, then (by induction) all the complex terms in $T(n)$ will cancel, for all integer $n$.

For example, consider the recurrence $T(n) = 2T(n-1) - 2T(n-2)$, with base cases $T(0)=0$ and $T(1)=2$. The characteristic polynomial of this recurrence is $x^2-2x+2$, so the solution is $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ for some constants $\alpha$ and $\beta$. Plugging in base cases gives us $$ T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\ T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2 $$ which implies $$ \alpha + \beta = 0 \\ \alpha - \beta = -2i $$ which implies $\alpha = -i$ and $\beta = i$. So the solution is $$ T(n) = i\cdot ((1-i)^n - (1+i)^n). $$

This function oscillates between $\sqrt{2}^n$ and $-\sqrt{2}^n$ with a "period" of 4. In particular, we have $T(4n) = 0$ for all $n$, because $(1-i)^4 = (1+i)^4 = -4$ (and because I chose the base case $T(0)$ carefully).

$\endgroup$
  • 1
    $\begingroup$ I seem to remember that imaginary roots of the characteristic polynomial (which are, if I remember correctly, the sequence's generating function's dominating singularities) imply negative elements somewhere. Is that true? If so, it is safe to say you should never encounter this case in algorithm analysis. $\endgroup$ – Raphael Mar 31 '12 at 12:23
  • 6
    $\begingroup$ Not necessarily. If the roots of the characteristic function are $2$, $1+i$, and $1-i$, for example, the function will oscillate around $\alpha 2^n$ for some $\alpha$, but (with appropriate base cases) it will always be positive. $\endgroup$ – JeffE Mar 31 '12 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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