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.

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$

I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. So if you are going to go by the guess method too, tell me how should I have made that guess?

Or, I'm actually more interested in knowing some other method that can possibly be used to solve that.

Thanks!

share|improve this question
    
Looking at the file you provided, they don't solve the recurrence either, the question and the answer there are to give a big-$O$ of bound for $T(n)$. If that is what you are after, you should say so in your question. I've tagged with "asymptotics". Also the file mentions a Master Theorem which you apparently should know about (mention that as well!), so it's not pure guessing. –  Marc van Leeuwen Oct 2 '12 at 5:33
    
@MarcvanLeeuwen, yes. Thank you for pointing out. Corrected :) –  GrowinMan Oct 2 '12 at 5:35

1 Answer 1

$n=2^m$ and let $T(2^m) = f(m)$.

We then have \begin{align} f(m) & = 4 f(m-1) + \dfrac{4^m}m = 4 \left( 4f(m-2) + \dfrac{4^{m-1}}{m-1}\right) + \dfrac{4^m}m\\ & = 16 f(m-2) + 4^m \left( \dfrac1{m-1} + \dfrac1m \right)\\ & = 16 \left( 4f(m-3) + \dfrac{4^{m-2}}{m-2}\right) + 4^m \left( \dfrac1{m-1} + \dfrac1m \right)\\ & = 64f(m-3) + 4^m \left( \dfrac1{m-2} + \dfrac1{m-1} + \dfrac1m \right)\\ \end{align} So proceeding like this we finally get \begin{align} f(m) & = 4^{m} f(0) + 4^m \left(1+\dfrac12 + \dfrac13 + \cdots + \dfrac1m \right) \\ & \approx 4^{m} f(0) + 4^m \left(\log_e(m) + \gamma\right) \end{align} Plugging in $m = \log_2(n)$, we get $$T(n) \approx n^2 \log_e(\log_2(n)) = \mathcal{O} \left( n^2 \log(\log n)\right)$$

share|improve this answer
    
This is good. Is there a general rule for that kind of substitution or something? –  GrowinMan Oct 2 '12 at 5:50
    
@GrowinMan Well... I don't know. In general, if you have $T(n)$ related to $T(n/k)$, take $n=k^m$ and set $f(m) = T(k^m)$. Hence, you related $f(m)$ to $f(m-1)$ and proceed. –  user17762 Oct 2 '12 at 5:54

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.