World's most popular travel blog for travel bloggers.

Not convincing claim for Master Theorem Case 3

, , No Comments
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.

Asked By : Joel
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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback