Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n\in\mathbb{N}$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\log(n)$ steps. For which values of $n$ does insertion sort beat merge sort?
simple calculation using logs
1
$\begingroup$
algorithms
logarithms
-
1It's equivalent to solving n<8\log(n). Assuming the logarithm is 2-based, if $2\leq n\leq 32$, the inequality holds. The exact range can be approximated numerically. – 2012-03-01
1 Answers
2
Solving $8n^2 \lt 64n\log(n)$ (equivalently, $n\lt 8\log(n)$) exactly requires use of Lambert's W function. Solving it approximately is pretty easy.
At $n=1$, $8n^2\gt 64n\log(n)$; at $n=2$, $8n^2 \lt 64n\log(n)$; if $\log$ is base $2$, then they cross again at about $n=45$.