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?

  • 2
    $\begingroup$ You divided by 64 not by 64n. $\endgroup$ – hamam_Abdallah Dec 17 '18 at 20:01
  • $\begingroup$ I can't divide by 64n because I canceled n in 64n out in the first step $\endgroup$ – Evan Kim Dec 17 '18 at 20:05
  • 2
    $\begingroup$ @EvanKim $\frac n8=\log n$ $\endgroup$ – Shubham Johri Dec 17 '18 at 20:11
  • $\begingroup$ Oh I see it now $\endgroup$ – 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$.

  • $\begingroup$ Forgive me for my question, but why did you use log$e$? $\endgroup$ – Evan Kim Dec 18 '18 at 0:45
  • $\begingroup$ @EvanKim Because the logarithm is in base 10. $\endgroup$ – egreg Dec 18 '18 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.