Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.