limits - Is $nlog(n)+mlog(m)=O(nlog(m)+mlog(n))$? And what about $nlog(m)+mlog(n)=O(nlog(n)+mlog(m))$?

I am trying to decide if each of these two statements are true or false:

• 
  

  $n\log(n)+m\log(m)=O(n\log(m)+m\log(n))$

  
  


• 
  

  $n\log(m)+m\log(n)=O(n\log(n)+m\log(m))$

  
  

I've tried using some properties of logarithms so as to take these two statements to these inequalities:

• For the first one, the statement is true if and only if there exist $c$ and $(n_0,m_0)$ such that for all $(n,m)>(n_0,m_0)$ (which means $n>n_0$ and $m>m_0$)

$$n^n* m^m \leq c(m^n* n^m)$$ $${n}^{n-m}\leq cm^{n-m} $$

If I take $m=m_0+1$ and $n=(n_0+1)(m_0+1)c$ then $(n,m)>(n_0,m_0)$ but $$n^{n-m} > cm^{n-m}$$

From here it follows that the first statement is false.

• As for the second one, the statement is true if and only if there exist $c, (n_0,m_0)$ such that for all $(n,m)>(n_0,m_0)$ $$m^n*n^m \leq c(n^n*m^m)$$ $$n^{m-n} \leq cm^{m-n}$$

I got stuck at this part, I would appreciate some help to prove or disprove the second statement and also to know if I've done the first part correctly. Thanks in advance.

Answer

Since the functions being compared are functions of two variables, $m$ and $n$ it seems the answer would depend entirely upon whether $m$ and $n$ are of the same order.

Let $m=nk$. Then $k=\dfrac{m}{n}$.

The question of whether

$$ n\log(n)+m\log(m)=O(n\log(m)+m\log(n)) $$

becomes a question of whether

$$ n\log(n)+nk(\,\log(n)+\log(k)\,)=O(\,n\log(n)+n\log(k)+nk\log(n\,) $$ which reduces to the question whether

$$ k\cdot(n\log(n))=O(n\log(n)) $$

And since $k=\dfrac{m}{n}$ this reduces to the question whether

$$ m\log(n)=O(n\log(n)) $$

Next consider the second quesion. Is

$$ n\log(m)+m\log(n)=O(n\log(n)+m\log(m)) $$

Taking the same approach as in the first question, this reduces to the question of whether

$$ n\log(n)=O(m\log(n)) $$

So it comes down to whether or not $m$ and $n$ are of the same order.

So, for example, if $m=O(x^3)$ and $n=O(x^2)$ then the two functions are not of the same order. But if $m=O(x^2)$ and $n=O(x^2)$ then the two functions are of the same order.