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.

If we have an algorithm with complexity $\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 with complexity $\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
    
What does $\theta$ notation mean? –  Godot Dec 26 '12 at 13:37
1  
@Godot: I suppose that should actually be $\Theta$, not $\theta$. –  Ilmari Karonen Dec 26 '12 at 14:58

1 Answer 1

up vote 3 down vote accepted

I assume that, by $\Theta$, you mean this notation.

From $f(m,n) \in \Theta(m \log n)$ and $0 < m < n^2$, we can conclude that $f(m,n) \in O(n^2 \log n)$. We cannot conclude $f(m,n) \in \Theta(n^2 \log n)$, since it's possible that $m \in o(n^2)$. For example, if $m = n$, then $f(m,n) \in \Theta(n \log n)$.

The reason we could conclude from $f(m,n) \in \Theta(m + n^2)$ and $0 < m < n^2$ that $f(m,n) \in \Theta(n^2)$ is that, even if $m \in o(n^2)$, the expression $m + n^2$ still contains an $n^2$ term which will dominate any smaller $m$. That is, we already know that $\Theta(m + n^2) \subset \Omega(n^2)$, and $m < n^2$ implies that $\Theta(m + n^2) \subset O(n^2)$, and thus $\Theta(m + n^2) \subset (\Omega(n^2) \cap O(n^2)) = \Theta(n^2)$.

However, if we know that $m \in \Theta(n^2)$, then we can indeed conclude from $f(m,n) \in \Theta(m \log n)$ that $f(m,n) \in \Theta(n^2 \log n)$.

share|improve this answer
    
Yes as you guess it's big theta. Tnx for your clear and complete explanation. I will vote up as soon as i get 15 reputation. –  Sajjad Dec 26 '12 at 16:37

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.