Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

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

share|improve this answer
    
You would mind pointing me to the example, I can't seems to find it. Thanks –  newprint Sep 11 '12 at 22:41
    
This answer is self contained. –  Did Sep 12 '12 at 5:15
    
shouldn't it be natural logarithm? –  Alex Nov 12 '12 at 1:01
    
First, it is. Second, it does not matter. –  Did Nov 12 '12 at 7:27

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.