5
$\begingroup$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq dn^{2}\log_{2}(n)$ but I can not find mathematical way to prove that, is there any trick with logarithms that I can use?

  • 0
    What does θ mean? Is it a typo (T(n^2))?2010-11-15
  • 0
    Θ is Big Theta notation but we can just say T(n)=2*T(n/2)+T(n/3)+n^22010-11-15
  • 1
    Please excuse me, and what is d?2010-11-15
  • 0
    it is a constant2010-11-15
  • 0
    Hi @ECE, I don't think that bound is correct. Even at the first level, you are doing θ(n^2) work, so how can you bound the entire recurrence with O(n lg n)?2010-11-15
  • 0
    not O(nlgn) but O(n^2*lgn)2010-11-15
  • 0
    Ah I see. Anyone with edit rights that can come through and tex-ify the math?2010-11-15
  • 1
    What are tree analyses?2010-11-15

3 Answers 3