1

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?

Yadati Kiran
  • 2,320
Evan Kim
  • 2,399

1 Answers1

1

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

egreg
  • 238,574