1
$\begingroup$

Suppose I have a function with two input below.

$f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$.

Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^2)$ instead? I think the first one is more representative as it includes the variable $m$. But that may not be the case if $n$ is relatively very larger than $m$.

$\endgroup$
2
$\begingroup$

No, it's not safe to say either. The intuition: When $n$ is really large, $f(m,n)$ grows faster than $O(m \log n)$. When $m$ is really large, $f(m,n)$ grows faster than $O(n^2)$.

Instead, what you can say is that $f(m,n)$ is $O(m \log n + n^2 + n \log \log m)$. Why?

$$\begin{align*} f(m,n) &= \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000\\ &=m \log n + 100n\log \log m + 100n\log 5 + 150m + 4n^2 + 1000\\ &=O(m \log n) + O(n \log \log m) + O(n) + O(m) + O(n^2) + O(1)\\ &=O(m \log n) + O(n \log \log m) + O(n^2) + O(m \log n) + O(n^2) + O(1)\\ &=O(m \log n + n \log \log m + n^2). \end{align*}$$

If $n \log \log m = O(m \log n + n^2)$ (I'm not sure if this is true), then you could simplify this to $O(m \log n + n^2)$.

$\endgroup$
  • $\begingroup$ $O(n\log\log m)$ cannot be changed to $O(n^2)$. A lemma like the following is required. $n\log\log m < m \log n + n^2$ if either $n$ is larger enough or $m$ is large enough. This lemma is, in fact, not immediate to prove although it might be intuitively clear for experienced users. $\endgroup$ – Apass.Jack Mar 20 at 22:17
  • $\begingroup$ @Apass.Jack, oh, good point! I'm not sure either. Edited. $\endgroup$ – D.W. Mar 20 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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