Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?

Question

I am trying to optimize the number of comparison in the merge sort algorithm, particularly during the merging step.

Is $a\log_2(b) \le b\log_2(a)$ for all $a$ and $b$ given that $1 \le b \le a$?

I plugged values of $a=2$ and $b=1$ and $2\log(1) \le 1\log(2)$ is true because $0\le1$, but I don't believe this is enough proof. Are there some values of $a$ and $b$ where this is not true?

if that is true, how to prove it mathematically ?

Answer 1

In most cases, the reverse inequality holds.

The inequality $a \log_2 b \le b \log_2 a$ is equivalent to $\frac a{\log_2 a} \le \frac{b}{\log_2 b}$, so we should look at the function $f(x) = \frac{x}{\log_2 x}$,

The derivative of $f(x)$ is $f'(x) = \frac{\log_2 x - \frac1{\ln 2}}{(\log_2 x)^2}$, or $\frac{\log_2 (x/e)}{(\log_2 x)^2}$. This is positive when $x>e$, and negative when $x<e$.

I will assume $a,b$ are integers. Then if $3 \le b \le a$, we have $f(b) \le f(a)$ because $f$ is increasing on this range, so in fact the reverse inequality holds: $a \log_2 b \ge b \log_2 a$.

We can check the remaining cases separately:

• If $b=1$, then $a \log_2 b$ simplifies to $0$ and $b \log_2 a$ simplifies to $\log_2 a$, so $a \log_2 b \le b \log_2 a$ for all $a \ge 1$.
• If $b=2$, then $a \log_2 b$ simplifies to $a$, and $b\log_2 a$ simplifies to $2 \log_2 a$. We have $a \le 2 \log_2 a$ only for $2 \le a \le 4$; for $a \ge 5$, $a \log_2 b > b \log_2 a$.

Answer 2

Since log is monoton you have $b^a\le a^b$ which is wrong for example for $b=1 ,a=2$