Can you help me understand the missing steps in solving this inequality for n

Question

[Updated]

I’m working on exercise 1-2.2 from Introduction to Algorithms, 3rd Edition:

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?

I am having a hard time following the solution given here.

$$ \begin{align} 8 n^2 &< 64\,n\,log_2{n} \tag{1}\\ 2^n &< n^8 \tag{2} \\ n &\le 43 \tag{3} \end{align} $$

I don’t understand how line 1 leads to line 2, and line 2 to line 3.

On my own I got from line 1 to $n \lt 8\,log_2n$ but I don’t see where to go from there.

Answer 1

\begin{align} 8n^2 &< 64 n \lg n \\ n & < 8 \lg n & \text{divide both sides by $8n$} \\ 2^n &< 2^{8 \lg n} = n^8 &\text{exponentiate both sides}. \end{align} The last line $n \le 43$ comes from some guess-and-check.

Answer 2

Since $n> 0$ we can devide both sides by $8n$ so it becomes:

$$n<8\lg(n)$$

Since $\lg(n)=\log_2(n)$ (I prefer this notation):

$$n<8\log_2(n)$$

Now we use a property of logarithms:

$$b\log(a)=\log(a^b)$$

So:

$$n<\log_2(n^8)$$

Applying the exponential in base $2$ to both terms:

$$2^n<n^8$$

:)