Solve the recurrence $T(n) = 5T(n/5) + n/\log(n)$

Question

$T(n) = 5T(n/5) + n/\log(n)$

I tried everything but I can't solve this recurrence.

I would love to know a way using the masters theorem.

Answer 1

Hint:

$T(n) = 5T(n/5) + n/\log(n) = 5(5T(n/25) + (n/5)/(\log (n/5))) +n/\log n$

$= 5T(n/25) +n/\log (n/5) +n/\log (n) = \cdots= 5^iT(n/5^i) +\sum_{j=1}^{i−1} n/\log (n/5^j).$

When $i= \log_5n$ the first term reduces to $5^{\log_5n}T(1)$.

Answer 2

Making $n = 5^m$ and substituting we have

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

or equivalently

$$ R(m) = 5 R(m-1) +\frac 1m 5^m $$

The homogeneous has as solution $R_h(m) = c_0 5^m$ making a particular with structure $R_p(m) = c_0(m)5^m$ and substituting into the complete recurrence we get

$$ c_0(m) = c_0(m-1) - \frac 1m $$

with particular solution

$$ c_0(m) = \sum_{k=1}^m \frac 1k = H_m $$

hence

$$ R(m) = (c_0+H_m)5^m $$

and going backwards with $m=\log_5 n$ we have

$$ T(m) = (c_0+H_{\log_5 n})5^{\log_5 n} = (c_0+H_{\log_5 n})n $$