My textbook shows that when setting up a recursion tree for a recurrence, like

$$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$

you place the cn^2 term at the root to represent the cost of at the top level of recursion and the three subtrees of the root represent the costs incurred by the subproblems of size n/4.

Why do you place cn^2 at the root? How do you know that the term cn^2 should be at the root of the recursion tree?

  • $\begingroup$ Your problem is not with the recurrence as is, but with the idea behind the recursion tree method. I recommend you revisit your course material; these notes by @JeffE may be useful. $\endgroup$ – Raphael Oct 27 '14 at 18:24
  • $\begingroup$ @Raphael: thanks for the link, these explanations are really clear! Which book does it come from? It's so much better than the Intro to Algorithms book by Cormen. (Actually, I just noticed the author's name, Jeff Erickson) $\endgroup$ – MNRC Oct 27 '14 at 18:49
  • $\begingroup$ As far as I know, these are the lecture notes of Jeff Erickson. Maybe he'll make a book out of them at some point. $\endgroup$ – Raphael Oct 28 '14 at 7:21
  • $\begingroup$ If you wanted to represent the execution of a recurrence of a tree then every node would hold in it the amount of work to be executed immediately (i.e., the amount of work not part of the inductive part of the recurrence). In this case, that would be your $cn^2$. Your recurrence would take the sum of work over all nodes in the tree. Since your first execution of the recurrence does $cn^2$ work, you would have your root perform $cn^2$ work and the descendants of the tree performing the remainder of the work. $\endgroup$ – Francesco Gramano Nov 5 '14 at 20:38
  • $\begingroup$ @FrancescoGramano Consider turning this into an answer? $\endgroup$ – Rick Decker Jan 6 '16 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.