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?
Recurrence relation with a number value (not n)
recurrence relation
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})$.