Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In a practice exam given in class, we were asked to solve the following recurrence
$$T(n) = 2T(n/4) + \frac{n}{\log n}$$
The given solution claims that this falls in the third case of the Master Theorem and starts with the following claim:
$$f(n) = n / \log n = \Omega (n^{1/2 + \epsilon}) \ \textrm{for any} \ 0 < \epsilon < 1/2$$
Is there a quick way to show this holds. Seeing the $\log n$ is the reason why I am doubting this claim.
Yes, this holds since $\log n = O(n^\epsilon)$ for any $\epsilon > 0$. You can prove this formally as follows. We will show that $\log n = o(n^{1/k})$ for all $k > 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. $$
