2
$\begingroup$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$.
Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came up with $n(\frac{1}{\ lgn} + \frac{1}{\lg (n/5^2)}+...+\frac{1}{ \ lg5} + 5T(1)) = nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am not sure how to express the the asymptotics/running time of the last expression.
Thanks!

2 Answers 2

1

Not sure I agree with your unrolling... Anyway, if you browse the site, you will discover that a rigorous method is explained on several pages, which is as follows. Consider $S(k)=T(5^k)/5^k$, then $S(k)=S(k-1)+1/(k\log5)$ hence $S(k)=S(0)+H_k/\log5$, where $H_k=\sum\limits_{i=1}^k1/i$ is the $i$th harmonic number. Note that $T(5^k)=5^kH_k/\log5+5^kT(0)$ and that $H_k/\log k\to1$. Thus, $T(5^k)=\Theta(5^k\log k)$.

Finally, assuming for example that $(T(n))_n$ is monotone, one gets $T(n)=\Theta(n\log\log n)$.

  • 0
    First, it is. Second, it does not matter.2012-11-12
1

This is probably just a variation/simplification of Didier's answer. If $T(1)=c_1$ is a constant, then all you need is Harmonic series: $\sum_{k=1}^{n}\frac{1}{k}=O( \ln n)$. Hence, $ S_n = c_1 n + O(n \ln \log_{5}n)=O(n \ln \log_{5}n) $ since $\lim_{n \to \infty}\frac{n \ln \log_{5}n}{n}=\infty$