Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

If we have an algorithm such that its complexity is $\Theta(m + n^2)$ and we know that $0 < m < n^2$, then its complexity becomes $\Theta(n^2)$. But if we had an algorithm such that its complexity was $\Theta(m\log n)$ and $0 < m < n^2$, could we conclude that its complexity is $\Theta(n^2\log n)$?

share|improve this question

migrated from cstheory.stackexchange.com Dec 26 '12 at 13:31

This question came from our site for theoretical computer scientists and researchers in related fields.

3  
This is not a research level question, though a nice exercise for an undergraduate course. Please check cstheory.stackexchange.com/faq for more information. –  Yixin Cao Dec 26 '12 at 12:26
    
yes. Reread the definition of the $O$ notation. There are many posts in cs.stackexchange.com with similar content. –  AJed Dec 26 '12 at 16:48
2  
@AJed The OP is asking about $\Theta$ (not $O$), which also requires $\Omega$ notation. That is probably why Yixin calls it a nice exercise. I believe the answer is actually no because of the lower bound. –  mayank Dec 26 '12 at 17:34
    
@mayank oh yes, I didnt see this. –  AJed Dec 26 '12 at 20:19

1 Answer 1

up vote 5 down vote accepted

If $m=\Theta(n^2)$, then indeed $\Theta(m\log n)=\Theta(n^2\log n)$.

However, you are only given that $0<m<n^2$, that is, $m=O(n^2)$ and you can only infer that the algorithm has complexity $O(n^2 \log n)$, but not $\Theta$ of the same quantity. For instance, assume $m$ is a constant, or assume $m=\sqrt{n}$, and you could see why it cannot be $\Theta(n^2\log n)$.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.