0
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ OK, this was off-topic on CS Theory but you got your answer there. Why do you need to ask again? $\endgroup$ – David Richerby Oct 20 '13 at 13:07
  • $\begingroup$ Because I was looking for a detailed answer which was not found there but I sure did get here. $\endgroup$ – Eran Oct 20 '13 at 17:53
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As it happens, this also works for all real $n\geq 0$. For $n\geq 1$, your argument applies; for $0\leq n\leq 1$, we have $n^4+2n \geq 2n \geq n^2$. $\endgroup$ – David Richerby Oct 20 '13 at 13:49
  • $\begingroup$ @DavidRicherby Good point! $\endgroup$ – usul Oct 20 '13 at 17:12
  • $\begingroup$ I've got so freaking confused. The functions were supposed to be of $\log()$ :\ $\endgroup$ – Eran Oct 22 '13 at 12:20
  • $\begingroup$ I don't understand, what do you mean? $\endgroup$ – usul Oct 22 '13 at 13:21
  • $\begingroup$ I was supposed to prove $\log(n^4+2n) = \Omega (\log(n^2))$ $\endgroup$ – Eran Oct 22 '13 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.