# Algorithm time complexity

Supposing I have an insertion-sort algorithm with a cost function $$8n^2$$ and a merge-sort algorithm with a cost function $$64n\log_2n$$, for which n values is better to execute the insertion-sort?

I've tried doing $$8n^2<64n\log_2n$$ and found $$2 but I can't seem to find a way to properly isolate n. Is this result satisfactory?

Use standard Calculus methods to sketch a graph of $$f(n) = n^{8/n}$$.
$$f'(n) = -8n^{-2 + 8/n}(\ln(n) -1)$$ We find a critical point at $$n = \mathrm{e}$$, so expect a maximum at $$n = 2$$ or $$n = 3$$. Further, $$f$$ is monotonically increasing on $$(0,\mathrm{e})$$ and monotonically decreasing on $$(\mathrm{e},\infty)$$. Also, $$\lim_{n \rightarrow \infty} f(n) = 1 \text{,}$$ so $$f$$ is initially less than $$2$$, is greater than $$2$$ on an interval, then is forever after less than $$2$$.
We should explicitly check $$n = 1, 2, 3$$: \begin{align*} f(1) &= 1^{8/1} = 1 \text{,} \\ f(2) &= 2^{8/2} = 16 \text{, and} \\ f(3) &= 3^{8/3} = 18.720{\dots} \text{.} \end{align*}
So restricting $$f$$ to the positive integers, it has a maximum at $$n = 3$$. It then decreases. We perform (initially) unbounded binary search to find where $$f$$ decreases through $$2$$.
\begin{align*} f(6) &= 10.90{\dots} \text{,} \\ f(12) &= 5.24{\dots} \text{,} \\ f(24) &= 2.88{\dots} \text{,} \\ f(48) &= 1.90{\dots} \text{,} \\ f(36) &= 2.21{\dots} \text{,} \\ f(42) &= 2.03{\dots} \text{,} \\ f(45) &= 1.96{\dots} \text{,} \\ f(43) &= 2.01{\dots} \text{, and} \\ f(44) &= 1.98{\dots} \text{.} \end{align*} We find that $$f(n) > 2$$ for $$2 \leq n \leq 43$$.
• Instead of exponentiating to get the final inequality, we can stop when at $$n < 8 \log_2 n,$$ which is a bit easier to work with. I decided not to make it a separate answer, though, since the technique ends up being about the same. Apr 3, 2021 at 1:42
• I will add that $n < 8 \log_2 n$ strongly suggests probing using powers of 2, rather than strict bisection. It's clear that $n=2$ works and $n=2^8=256$ does not. From there, trying $n=2^7, 2^6, 2^5$, etc., you quickly find that it's between $32$ and $64$. From there, proper bisection can take over. Apr 3, 2021 at 1:52