This question already has an answer here:

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?


marked as duplicate by D.W., FrankW, Raphael Oct 29 '14 at 6:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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})$.


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