Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Recurrence relation with a number value (not n)

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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