Upper and Lower bound of the recursive relation

[evinda]

Hello! (Wave)

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=5 T(\frac{n}{5})+\frac{n}{ \lg n}$.

I thought that I could use the master theorem,since the recursive relation is of the form $T(n)=aT(\frac{n}{b})+f(n)$

$$a=5 \geq 1 , b=5>1 , f(n)=\frac{n}{ \lg n}$$

$$f'(n)=\frac{ \lg n-1}{ \lg^2 n}>0 \Rightarrow \lg n >1 \Rightarrow n>2$$

So, $f(n)$ is asymptotically positive and increasing $\forall n>2$.

$$n^{\log_b a}=n^{\log_5 5}=n$$

We see that $f(n) < n$

$$f(n)=O(n^{ \log_b a- \epsilon})=O(n^{1- \epsilon})$$

But how can we find the $\epsilon$ ? (Thinking) Or can't we apply in this case the master theorem? (Worried)

 

[evinda]

I think that the master theorem cannot be applied. (Shake)

But..we could do it with substitution,right? (Thinking)

We set $m= \log_5{n} \Rightarrow n=5^m$

Then,we have:

$$T(5^m)=5T(5^{m-1})+\frac{5^m}{m} \\ \Rightarrow \frac{T(5^m)}{5^m}=\frac{T(5^{m-1})}{5^{m-1}}+\frac{1}{m}$$

Let $S(m)=\frac{T(5^m)}{5^m}$

So:

$$S(m)=S(m-1)+\frac{1}{m} \\ S(m-1)=S(m-2)+\frac{1}{m-1} \\ \dots \\ \dots \\ S(2)=S(1)+\frac{1}{2} \\ + --------------- \\ \Rightarrow S(m)=S(1)+\left ( \frac{1}{2}+ \dots + \frac{1}{m}\right )$$

But,how could we continue? (Thinking)