Tweeted twitter.com/StackCompSci/status/918264557935775745
5 edited title
| link

Asymptotic analysis of a real-valued function withinvolving complex numbers

4 edited tags
| link
3 edited body
source | link

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
source | link
1
source | link