# Asymptotic complexity of function with two Input variables

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

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)$$.
• $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. – John L. Mar 20 '19 at 22:17