# Find $n$ in a log equation

I am having trouble solving this problem.

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 $$64 n\log n$$ steps. For which values of $$n$$ does insertion sort beat merge sort?

*$$\log$$ is log base $$10$$

$$\rightarrow 8n^2 = 64n\log n$$ Divide both sides by $$n$$
$$\rightarrow 8n = 64\log n$$ Divide both sides by $$64$$
$$\rightarrow \frac{1}{8} = \log n$$
$$\rightarrow \log_{10}n = \frac{1}{8}$$
$$\rightarrow n = 10^{\frac{1}{8}}$$

When I plug $$10^{\frac{1}{8}}$$ in as $$n$$, I get $$14.215 = 10.649$$ so this doesn't seem to add up. Can someone help me understand what I am doing wrong?

• You divided by 64 not by 64n. – hamam_Abdallah Dec 17 '18 at 20:01
• I can't divide by 64n because I canceled n in 64n out in the first step – Evan Kim Dec 17 '18 at 20:05
• @EvanKim $\frac n8=\log n$ – Shubham Johri Dec 17 '18 at 20:11
• Oh I see it now – Evan Kim Dec 17 '18 at 20:13

You have a wrong simplification: the inequality $$8n^2<64n\log n$$ becomes $$n<8\log n$$ You can check that the function $$f(x)=8\log x-x$$ has a maximum at $$8\log e\approx 3.47$$, and so it is decreasing for $$x>8\log e$$. Thus when you have found $$n\ge 4$$ satisfying the inequality, with $$n+1$$ not satisfying it, you're done.
We have $$8\log 6\approx6.22>6$$ and $$8\log 7\approx6.76<7$$.
• Forgive me for my question, but why did you use log$e$? – Evan Kim Dec 18 '18 at 0:45