Why $ 2n^2\;log\;n+3n^2 \notin \Omega(n^3)$ ? We can choose constant $c=1$ and $n\ge1$ and the inequality will be true.
Asked
Active
Viewed 36 times
0
-
Do you think $2n^2\log n + 3n^2 \geq n^3$ for all $n \geq 1$? – Antonio Vargas Oct 22 '15 at 04:00
-
What are $x$ and $c$? – DirkGently Oct 22 '15 at 04:00
-
@AntonioVargas I am bad at this. How do you know exactly when inequality is true for all values of $n$? – Altaïr Oct 22 '15 at 04:02
-
@DirkGently I am sorry $x$ was mistake. I meant $n$. – Altaïr Oct 22 '15 at 04:03
1 Answers
0
When compared to polynomials, logarithms are vastly smaller. For instance, $\log^{100} x < x^{1/100}$ for sufficiently large $x$.
So for loose asymptotics, it's not unreasonable to "ignore logs." So morally, you are asking if $n^2 > c n^3$ for some positive constant $c$ and sufficiently large $n$, and this is clearly not the case.
Another common replacement is to replace $\log x$ by $x^{\epsilon}$ for some really small $\epsilon$. If you want to be concrete, perhaps $\epsilon = 0.01$. Then you're asking about $n^{2.01} > c n^3$, which is also clearly not the case for large $n$.
davidlowryduda
- 91,687