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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Welcome! Note that you can use LaTeX by $...$. $\endgroup$
    – Raphael ♦
    Mar 31, 2012 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, 2012 at 10:40
  • 6
    $\begingroup$ He's adopted the physicist's habit of misspelling $i$. $\endgroup$
    – JeffE
    Mar 31, 2012 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, 2012 at 5:23

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
2
  • 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, 2012 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, 2012 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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