- #1

evinda

Gold Member

MHB

- 3,836

- 0

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)