I reading "Introduction to Algorithms", where I asked solve exercise (ex. below)
"Suppose we are comparing implementations of insertion sort and merge sort on the
same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge
sort runs in $64n \lg {n}$ steps. For which values of $n$ does insertion sort beat merge
sort?"
So I peek solution:
$8n^2<64n\log_2(n) \implies n^2<8n\log_2(n) \implies n\leq43$
Please somebody explain me how from $n^2<8n\log_2(n)$ get to $n\leq43$.
Best Answer
$$n^2 < 8n \log_2(n)$$
The inequality is false for $n=1$ and $n=2$
However, for $n \ge 3$ notice that $\frac{x}{\ln x}$ is an increasing function:
$$n < 8 \log_2(n)$$
$$\frac{n}{\log_2(n)} < 8 $$
We can then use bisection search to find such value