World's most popular travel blog for travel bloggers.

# Not convincing claim for Master Theorem Case 3

, ,
Problem Detail:

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.

###### Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53741

3200 people like this