patternMinor
Asymptotic analysis of a real-valued function involving complex numbers
Viewed 0 times
realinvolvinganalysisvaluedfunctionasymptoticnumberscomplex
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#82341, answer score: 3
Revisions (0)
No revisions yet.