0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – LostInSpace Sep 27 '17 at 22:42
  • $\begingroup$ @Isham Are you saying that n x log(m) < m x log(n) for m >>> n ?? $\endgroup$ – Adithya Upadhya Sep 27 '17 at 22:50
  • $\begingroup$ All of the bold face text is.... distracting. $\endgroup$ – Simply Beautiful Art Sep 27 '17 at 22:52
  • $\begingroup$ @oathkeeper for $m=(n+1) $...try $ (n+1)^n>n^{n+1} $ and see that it is false $\endgroup$ – LostInSpace Sep 27 '17 at 22:52
  • $\begingroup$ @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 :) $\endgroup$ – Adithya Upadhya Sep 27 '17 at 22:54
0
$\begingroup$

HINT

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Jam Sep 27 '17 at 23:07

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.