# Asymptotic analysis of a real-valued function involving complex numbers

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.

• Commented Oct 11, 2017 at 22:01

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.
• "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? Commented Oct 12, 2017 at 17:42
• 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. Commented Oct 12, 2017 at 18:42
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{.}$$