I was wondering how $n^3$ compares to $2n^2 \log n$ as I thought that $n^3$ is $\Omega(n^2 \log n)$
but there is the fact that $n$ is $O(n \log n)$ so I wasn't sure whether it is bigO or $\Omega$
Asked
Active
Viewed 2,317 times
3 Answers
2
I don't know what is $\Omega$, but a classical result says that $n^2\log n=o(n^\alpha)$ for all $\alpha>2$ (hence $n^2\log n=O(n^\alpha)$.
As for your assertion, $n=o(n\log n)$, not $O$.
Bernard
- 175,478
-
1$\Omega(\cdots)$ is the "opposite of" $O(\cdots)$. More precisely $f(n)$ is $\Omega(g(n))$ iff $g(n)$ is $O(f(n))$. – hmakholm left over Monica Aug 28 '15 at 12:20
-
1Also $n$ is indeed $O(n\log n)$ -- remember that $O(n\log n)$ is the class of functions that grow no faster than $n\log n$, but they are allowed to grow slower. – hmakholm left over Monica Aug 28 '15 at 12:22
2
Yes, $n^3$ grows asymptotically faster than $2n^2\log n$, so $n^3$ is $\Omega(n^2\log n)$.
This is the same as saying that $n^2\log n$ is $O(n^3)$, which should be well known -- since $n>\log n$ for all $n>0$, we have $n^3 \ge n^2\log n$ even before taking asymptotics.
hmakholm left over Monica
- 286,031
0
$n^3$ is $\Omega(n^2\log n)$ and $\Omega(n^{2.9995}\log^7n$ and $O(n^3)$ and $O(n^{17})$ and $O(n^3\log n).$ Remember that $O$ essentially means "not faster than" and $\Omega$ essentially means "not slower than".
Charles
- 32,122