Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to prove that $n^4+2n = \Omega (n^2)$
Which means I need to point two constants $c_1,c_2$ that from $n_0$: $$ c_1 \leq \frac{\log(n^4+2n)}{\log(n^2)} \leq c_2$$
Now I know that: $\lim_{n \to \infty } \frac{\log(n^4+2n)}{\log(n^2)} = 2$ so I can choose $c_1 = 0.5$ and $c_2 = 3$ but how do I do I calculate the $n_0$ that this sentence become true to?
You are working harder than you have to. There are lots of ways to prove this but in general the idea is that you should just find some constants that work, not worry about finding precise small constants.
In this case we don't even need constants! Assuming $n \geq 1$, we have $$n^4 + 2n \geq n^4$$ always. And $$n^4 \geq n^2$$ always.
So $n^4 + 2n \geq n^2$, which means $n^4 = \Omega(n^2)$.
...
An easier definition of $\Omega$ is that you need to find a positive constant $C$ so that $$C(n^4 + 2n) \geq n^2$$. As mentioned above, $C = 1$ works!
...
Finally, for your example, as in the comment on cstheory, if you want to do it your way, you can always just pick a really high $n_0$ and check that it does indeed work. In general, you can try to solve the equation $C(n^4 + 2n) = n^2$ for $n$, once you have picked a constant $C$ using your limit approach.
