# Dominant term and Big Omega

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?

-
What do you think is the dominant term of $1 + \log_2 n$? – Calvin Lin Jan 23 '13 at 6:07
My understanding of dominant terms from previous Calc classes is that it is the term which grows more rapidly, so I would have to guess $log_2(n)$. – user59323 Jan 23 '13 at 6:27
Then what is the dominant term of $n^3 + n^3 \log_2 n$? Hint: Factorize $n^3$. – Calvin Lin Jan 23 '13 at 6:32
Well it would factor to $n^3(1+log_2(n))$. Does that mean the dominant term of the function would be $n^3log_2(n))$? I think that's the part that's got me confused. – user59323 Jan 23 '13 at 6:41
Yes, that's the dominant term. – Calvin Lin Jan 23 '13 at 6:45

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$.

-
Great answer! That's the way Calvin was pushing me in his comments above, but this is a great explanation of the reasoning. The refresher on dominance helped me a lot. – user59323 Jan 23 '13 at 7:12