title: Solving a recurrence T(n) = 2T(n/2) + n^4
body: <p>I am studying using the MIT Courseware and the CLRS book <em>Introduction to Algorithms.</em></p>
  <p>I am currently trying to solve the recurrence (from page 107)</p>
  <blockquote>
  <p>T(n) = 2T(n/2) + n<sup>4</sup></p>
  </blockquote>
  <p>If I make a recurrence tree, I get:</p>
  <blockquote>
  <p>Level 0: n<sup>4</sup></p>
  <p>Level 1 2(n/2)<sup>4</sup></p>
  <p>Level 2 4(n/4)<sup>4</sup></p>
  <p>Level 3 8(n/8)<sup>4</sup></p>
  </blockquote>
  <p>The tree has lg(n) levels. Therefore I think that the recurrence should be</p>
  <blockquote>
  <p>T(n) = Θ(n<sup>4</sup> lg n)</p>
  </blockquote>
  <p>But, If I use the master theorem, I get that</p>
  <blockquote>
  <p>T(n) = Θ(n<sup>4</sup>)</p>
  </blockquote>
  <p>Clearly both of these can't be right.  Which one is correct?  And where did I go wrong with my reasoning?</p>