simple calculation using logs 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?

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