1
$\begingroup$

I'm learning an algorithm, the algorithm takes as input a graph of n vertices, and recurse on some subgraphs.

the complexity analysis done by the author is based on using recurrent formula.

the equation $T(n) = T(n - 3) + 2T(n - 4) + 4T(n - 6)$ was produced by reviewing the possible recursive calls.

the author says that by solving this recurrence, the unique real positive root of the polynomial $x^6=x^3+2x^2+4$ is approximately $1.51433$.

So the complexity of the algorithm is $O(1.51433^n)$.

My question is how we can produce the equation from the recurrence formula.

$\endgroup$
1
  • 1
    $\begingroup$ That reasoning is based on the characteristic polynomial of the recurrence. I'd suggest reading up on that if you'd like to know why it works. $\endgroup$ Commented Jun 20, 2019 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

Assume I would like to look for the solutions to the recurrence $T_n$ of the form $T_n = x^n$ for some $x \ne 0$. Plugging that into the recurrence, you get $$ x^n = x^{n-3} + 2x^{n-4} + 4x^{n-6} $$ and now cancel $x^{n-6}$ from both sides, yielding your polynomial.

Indeed, the resulting polynomial $x^6-x^3-2x^2-4$ has one positive root $r \approx 1.51432$ (as you can see on the Wolfram Alpha plot, so more accurately one would say that $$ T(n) = \Theta(r^n). $$

$\endgroup$
2
  • 1
    $\begingroup$ This question essentially asks why the roots of the characteristic polynomial of a recurrence yield the complexity. Your answer does not address this. $\endgroup$ Commented Jun 20, 2019 at 20:57
  • $\begingroup$ @Qudit No. The question is how we can produce the equation from the recurrence formula, not what you wrote. $\endgroup$ Commented Jun 20, 2019 at 21:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.