I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form

$$T(n) = aT\big(\frac{n}{4}\big) + n$$

I'm stuck when the equation has a numerical term, like

$$T(n) = aT\big(\frac{n}{4}\big) + 3$$

Using a recursion tree, what gets multiplied at the first, second, third level? And what is the sum of the work done?

  • $\begingroup$ I found a great explanation at Youtube as well (youtube.com/watch?v=N50-z_3m_O0) for anyone that needs a very thorough explanation for beginners. $\endgroup$ – MNRC Oct 28 '14 at 18:28
  • 1
    $\begingroup$ What have you tried? What self-study have you done? Have you read standard textbook material on how to solve recurrences? Have you read our reference questions, e.g., cs.stackexchange.com/q/2789/755? Have you tried using the Master theorem? (It covers this case.) I expect you to do a significant amount of research/self-study and to make a serious effort on your own before asking, and to show us in the question what you've tried and where you got stuck. There would not be a lot of point in having us repeat standard material that's already covered in many existing places. $\endgroup$ – D.W. Oct 28 '14 at 23:47

The recursion tree corresponds to repeated expansion of the recurrence: $$ \begin{align*} T(n) &= 3 + aT(n/4) \\ &= 3 + 3a + a^2T(n/16) \\ &= 3 + 3a + 3a^2 + a^3T(n/64) \\ &= \cdots \\ &= 3 + 3a + \cdots + 3a^{k-1} + a^kT(n/4^k) \\ &= 3\frac{a^k-1}{a-1} + a^kT(n/4^k). \end{align*} $$ This is the result if you stop the recursion after $k$ steps. If, for example, you define $T(1) = 3$ then for $n = 4^k$ you will get $T(n) = 3+3a+\cdots+3a^k = 3\frac{a^{k+1}-1}{a-1} = \Theta(a^{\log_4 n})$.

| cite | improve this answer | |

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