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.

A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it 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.

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