# Given m > n, how do we analyze $n*\log(m)$ vs $m*\log(n)$

The sizes of list A and B are $m$ and $n$ respectively. It's given that $m>n$, which implies that $\log(m) > \log(n)$. Therefore, $m\log(m)>n\log(n)$.

My question is about the analysis of $m\log(n)$ vs. $n\log(m)$ given $m>n$.

I am looking for general cases and a general solution for this problem. I am not even sure if there is a general solution for this problem.

An example algorithm problem:

Given two sorted lists A & B of size $m$ and $n$. Find $a ∈ A$ and $b ∈ B$ such that $a + b = K$.

Algorithm 1: Keep picking an element $a ∈ A$ and perform a binary search, looking for $K-a$ in List B until a solution is found. The complexity is $\mathcal{O}(m\log(n))$

Algorithm 2: Keep picking an element $b ∈ B$ and Perform a binary search, looking for $K-b$ in List A until asolution is found. Complexity $\mathcal{O}(n\log(m))$

So, which Algorithm is better, 1 or 2?

I hope that the solution is not to compute $m\log(n)$ and $n\log(m)$ numerically and decide on the basis of that. I'm looking for a general solution.

EDIT: Since we are dealing with asymptotic analysis (complexity analysis), Please consider that m & n are very very large.

• Try to prove the statement for $m=n+1$ and see if it's true that $m^n>n^m$ Well not true for m close to n but superior...since $( 1+ \frac 1 n)^n$ is less than e and not $>n$ – LostInSpace Sep 27 '17 at 22:42
• @Isham Are you saying that n x log(m) < m x log(n) for m >>> n ?? – Adithya Upadhya Sep 27 '17 at 22:50
• All of the bold face text is.... distracting. – Simply Beautiful Art Sep 27 '17 at 22:52
• @oathkeeper for $m=(n+1)$...try $(n+1)^n>n^{n+1}$ and see that it is false – LostInSpace Sep 27 '17 at 22:52
• @SimplyBeautifulArt Please edit the question to make it more beautiful without changing any content. I am not good at editing questions. Maybe you can help :) – Adithya Upadhya Sep 27 '17 at 22:54

Diving both by $\log(m) \cdot \log (n)$ and analyze the function $$f(x) = \frac{x}{\log x}$$ to show if it is increasing or decreasing using $f'(x)$... You are looking for asymptotics, so more interested in large values of $x$, but in general this analysis can show you a point where behavior changes, if one exists.
• To add to this, if you show that if $x>y$ means that $\frac{x}{\ln x}<\frac{y}{\ln y}$ or $\frac{x}{\ln x}>\frac{y}{\ln y}$, then this can tell you how to compare $\frac{n}{\ln n}$ and $\frac{m}{\ln m}$. – Jam Sep 27 '17 at 23:07