Not convincing claim for Master Theorem Case 3
Yes, this holds since $\log n = O(n^\epsilon)$ for any $\epsilon &gt; 0$. You can prove this formally as follows. We will show that $\log n = o(n^{1/k})$ for all $k &gt; 0$, or equivalently, that $\log^k n = o(n)$ for all $k \geq 0$. The proof is by induction. The base case $k = 0$, is clear. For the induction step, L'Hôpital's rule gives
$$
\lim_{n\to\infty} \frac{\log^k n}{n} = \lim_{n\to\infty} \frac{k\log^{k-1} n}{n} = 0.
$$