For which values of n does insertion sort beat merge sort?

Question

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$.

Answer 1

You are looking for the maximum $n$ such that $n \lt 8\log_2 n$. Generally we need to do numeric approximation for expressions like this that mix logs and polynomials. You can use the fact that the log is slowly increasing and just try. We can start by trying powers of $2$ so the log is easy to take. $n=32$ gives $32 \lt 40$, which is true. $n=64$ gives $64 \lt 48$, which is false. Now keep going, just cutting the interval in half each time. This is the bisection method, which is easy to understand and program, but takes more evaluations of the function than other approaches. You can also graph the two sides and look for the intersection.

Answer 2

$$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

Answer 3

As @Ross Millikan said, this equation cannot be solved linearly, but we can approximate to the solution using an numerical algorithm,like newton-raphon method:

$$x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)}$$

$8n^2<64n\log_2(n) \implies n^2<8n\log_2(n) \implies n<8log_2(n)$

Let $f(n) = n - 8log_2(n)$

The root of this function, is the value since where $n\geq 8log_2(n) $

Now we guess an initial value $x_0$ for the newton-raphson method, but we should be careful choosing this initial value, if we choose a wrong number this method won't converge.

In order to guess an initial value near the true solution, we'll choose two numbers: $$$$ $x_n $ and $ x_{n+1}$ where: $$$$ $x_n \lt x_{n+1}$ and $x_n<8log_2(x_n)$ is true and $x_{n+1}<8log_2(x_{n+1})$ is false.

$$$$

I'll do this choosing number on the succession $2^x$

$$$$ $2^2=4 < 8log_2(4)=8$, true $$$$ $2^3=8 < 8log_2(8)=24$, true $$$$ $2^4=16 < 8log_2(16)=32$, true $$$$ $2^5=32 < 8log_2(32)=40$, tue $$$$ $2^6=64 < 8log_2(64)=48$, false

Now we know that our solution is between $(32, 64)$, I'll set $x_0=\frac{32+64}{2} = 48$ and use newton-raphson method

$$$$ Recall $f(n) = n - 8log_2(n)$ and $f^{'}(n) = 1 - \frac{8}{nln2}$

$$$$

Step 0, $i=0$ $$$$ $x_1=48; f(48)=20$ $$$$ Step 1, $i=1$ $$$$ $x_2=43,63; f(43,63)=0,05$ $$$$ Step 2, $i=2$ $$$$ $x_3=43,55; f(43,55)=0,002$

$$$$ We stop at third interaction ande set $n=43$

$$$$ For $n=42$ $$$$ $42 < 43,67$, true $$$$ For $n=43$ $$$$ $43 < 43,41$, false $$$$ For $n=44$ $$$$ $44 < 43,67$, false $$$$ And so on, ..