0

$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.

User8976
  • 12,637
  • 9
  • 42
  • 107
Jurko Guba
  • 101
  • 1
  • 2
  • Welcome to MSE, Jurko. By Master's theorem, do you mean https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) ? – max_zorn Feb 10 '18 at 06:04
  • Your example is one of the inadmissible recurrences in the Wikipedia article on Master theorem. Try using Akra-Bazzi method. – Prasun Biswas Feb 10 '18 at 06:12
  • I'm voting to close this question as off-topic because this question belongs in https://cs.stackexchange.com/ (they need to add a few more sites of the SE network in the migration part of closing) – Prasun Biswas Feb 10 '18 at 06:55
  • Is there a solution for this? I'm having difficulties with this one as well. Tried Akra-Bazzi and stuck on the integral which I do not know how to evaluate –  Apr 14 '18 at 20:47

2 Answers2

1

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 $$

Cesareo
  • 33,252
0

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)$.

User8976
  • 12,637
  • 9
  • 42
  • 107