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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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