For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation.
$$n^3+n^2\log_2(n)+n^3\log_2(n)$$
So, I believe $n^3$ is the dominant term – but a plot of these shows that $n^3$ doesn't grow as fast as the function? Just starting a course in this and I still haven't got a solid grasp on it yet. I understood Big O should be an upper bound and Big Omega a lower. And how do I use the dominant term to determine the Big Omega?
Best Answer
Maybe thinking about it this way will help. The dominant term is the one which can be "factored out" and leave behind something bounded. Here,
$$ n^3 + n^2 \log_2 n + n^3 \log_2 n = n^3 \log_2 n \,\left(\frac{1}{\log_2 n} + \frac{1}{n} + 1\right) $$
The quantity in parentheses $\frac{1}{\log_2 n} + \frac{1}{n} + 1$ tends to $1$ as $n \to \infty$, so for any constants $C < 1 < D$ you can find an $N \in \mathbb{N}$ such that
$$ C < \frac{1}{\log_2 n} + \frac{1}{n} + 1 < D $$
for all $n \geq N$. In particular you find an $N \in \mathbb{N}$ such that
$$ \frac{1}{2} < \frac{1}{\log_2 n} + \frac{1}{n} + 1 < \frac{3}{2} $$
for all $n \geq N$, say. (The specific values $1/2$ and $3/2$ aren't too important.)
Thus, for $n \geq N$,
$$ \frac{1}{2} n^3 \log_2 n < n^3 + n^2 \log_2 n + n^3 \log_2 n < \frac{3}{2} n^3 \log_2 n. $$
This is precisely the statement that
$$ n^3 + n^2 \log_2 n + n^3 \log_2 n = O(n^3 \log_2 n) $$
and
$$ n^3 + n^2 \log_2 n + n^3 \log_2 n = \Omega(n^3 \log_2 n) $$
as $n \to \infty$.