Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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<n^{\frac{8}{n}}$ 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$.
