5 edited title

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

4 edited tags
3 edited body

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^4 - 1 = 0$$$$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.

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 roots of the equation $$z^4 - z^4 - 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.

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.

2 added 4 characters in body
1