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.

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