[Solved]: What can be said about Θ-classes in m and n if we know that m < n?

Problem Detail: 

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)$?

Asked By : Sajjad

Answered By : Ran G.

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7604

3.2K people like this

 Download Related Notes/Documents