4
$\begingroup$

I have an algorithm which computes the size of maximum independent set of a graph $G(V, E)$. Let $n=|V|$ be the number vertices, $m=|E|$ be number of edges, and denote the size of maximum independent set of the graph $G$ as $\alpha(G)$ .

Now, I want to estimate the worst-case running time the algorithm needs to compute $\alpha(G)$. I have come up with the following recurrence relation $$T(n) \leq T(n-1) + T(n-4) + O(n^2)$$ where $T(n)$ denotes the worst case running time. I also assume that the graph has in worst case $n^2$ edges. This algorithm makes two recursive calls and so I have $T(n-1) + T(n-4)$.

My approach is to solve the following inhomogeneous recurrence relation

$$a_n=a_{n-1}+a_{n-4} + n^2, \text{ where } a_0=a_1=a_2=a_3 = 1$$ This relation has two particular solutions $$a_n^* = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n$$ where $z_1,z_2,z_3,z_4$ are characteristic roots of the characteristic equation $z^4 - z^3 - 1 = 0$ and $$a_n^+ = B_2n^2 + B_1n + B_0$$ which gives the following general solution $$ a_n = a_n^* + a_n^+ = A_1z_1^n + A_2z_2^n+A_3z_3^n+A_4z_4^n + B_2n^2 + B_1n + B_0$$

My problem is that two of the roots $z_1,z_2,z_3,z_4$ are complex, one is real positive, and one is real negative, and I do not know how in general we estimate the rate of growth of functions having complex numbers like in this case. I would like to know if there is any general approach widely used in computer science and math to deal with such functions.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
3
$\begingroup$

Only the root(s) with largest magnitude matters (for generic initial conditions), and the asymptotic rate of growth is exponential in this magnitude (assuming no repeated roots). In your case this root is real, and it's a simple exercise to show that the others don't affect the asymptotic rate of growth.

A more complicated case is recurrences such as $a_n = a_{n-2}$. In this case there are two roots of largest magnitude, both complex. This corresponds to the periodic nature of the recurrence. Nevertheless, for generic initial conditions, the growth rate is $\Theta(1)$, agreeing with the first sentence above.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "asymptotic analysis is about real-valued functions" -- I'd say asymptotics is about things with limit processes. Any set for which you can define a reasonable $\lim$ operator would work, wouldn't it? $\endgroup$
    – Raphael
    Commented Oct 12, 2017 at 17:42
  • $\begingroup$ @Raphael No. You need an ordered field, which the complex numbers aren't. $\endgroup$
    – Yuval Filmus
    Commented Oct 12, 2017 at 18:32
  • 1
    $\begingroup$ They're about as ordered as $\mathbb{N}^2$. Anyway, I guess I was thinking about the parameter domain whereas you are talking about the value domain. So never mind. $\endgroup$
    – Raphael
    Commented Oct 12, 2017 at 18:42
1
$\begingroup$

Recall that complex numbers also have a polar representation. \begin{align*} z_k &= x_k + \mathrm{i} y_k \\ &= |z_k| \mathrm{e}^{\mathrm{i} \arg(z_k)} \\ &= \sqrt{x_k^2 + y_k^2} \mathrm{e}^{\mathrm{i} \cdot \mathrm{atan2}(y_k, x_k)} \text{,} \end{align*} where "$\mathrm{atan2}(y, x)$" is the (relatively common in programming libraries for math) version of arctangent that produces angles in all four quadrants (depending on the individual signs of $x$ and $y$ instead of just on the ratio $y/x$ as for normal arctangent). Then \begin{align*} z_k^n &= |z_k|^n \mathrm{e}^{\mathrm{i} n \arg(z_k)} \\ &= \left(x_k^2 + y_k^2\right)^{n/2} \mathrm{e}^{\mathrm{i} n \cdot \mathrm{atan2}(y_k, x_k)} \text{,} \end{align*} The $\mathrm{e}^{\mathrm{i} \dots}$ factor always has magnitude $1$, so $$ |z_k^n| = \left(x_k^2 + y_k^2\right)^{n/2} \text{.} $$

Improve this answer
$\endgroup$

Your Answer

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

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