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$ ? Or can't we apply in this case the master theorem?
EDIT:
Could I do it maybe,using the substitution method,like that:
$$m=\log_5 n \Rightarrow n=5^m$$
$$\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}$
Then: $$S(m)=S(m-1)+\frac{1}{m} \\ S(m-1)=S(m-2)+\frac{1}{m-1} \\ \dots \\ S(2)=S(1)+\frac{1}{2}$$
So,we get:
$$S(m)=S(1)+\frac{1}{2}+\frac{1}{3}+ \dots + \frac{1}{m-1}+\frac{1}{m}$$
But,how can I continue?
Here's some intuition about the master theorem.
Case $1$: If $f(n)$ is polynomially smaller than $n^{\log_b(a)}$, then it is negligible, and the asymptotic behavior is the same as what you would have without it included.
Case $2$: If $f(n)$ is either of the same order as or exactly logarithmically larger than $n^{\log_b(a)}$, then the two terms compound each other, and you pick up an additional asymptotic factor of $\log n$ on top of $f(n)$ itself.
Case $3$: If $f(n)$ is polynomially larger than $n^{\log_b(a)}$, then the recursive term is negligible, and the asymptotic behavior is the same as what you would have without it included.
In your case, $f(n)$ is asymptotically but not polynomially smaller than $n$, so it is bigger than case $1$ but smaller than case $2$. This means that you should expect $T(n)$ to be larger than what you would get in case $1$ (i.e. larger than $\Theta(n)$) but smaller than anything you might get from case $2$ (i.e. smaller than $\Theta(n \log n)$).
You can get a sharper result using the Akra-Bazzi method (http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method), which is a generalization of the master theorem. The sharp result is
$$T(n) = \Theta(n \log \log n)$$
which is consistent with the discussion above.