Solve the Recurrence Relation $T(n) = 2T(n/2) +T(n/4) + n^2$.

Question

I am trying to find the best way to solve $T(n)=2T(\frac{n}{2})+T(\frac{n}{4})+n^2$. I tried to use the recurrence tree method, and after adding up all the levels of the tree i get the summation below: $T(n)=n^2+\frac{9n^2}{16}+\frac{18n^2}{64}+\frac{36n^2}{256}+...$ When I try to find a closed form solution I get something like $288n^2$. Can I say that the recurrence is $\Theta(n^2)$?

Answer 1

To make things simple, we denote that $n = 2^k$ ($k$ is not necessarily $\in \mathbb{N}$) and the recurrent sequence becomes $$T(2^k) = 2T(2^{k-1}) + T(2^{k-2}) + 2^{2k} \tag{1}$$

Let's denote $f(k) = T(2^k)$, then $$\begin{align} (1)&\Longleftrightarrow f(k) = 2f(k-1) +f(k-2) + 4^{k} \\ &\Longleftrightarrow \left(f(k) - \frac{16}{7}4^k\right) = 2\left(f(k-1) - \frac{16}{7}4^{k-1}\right) +\left(f(k-2) - \frac{16}{7}4^{k-2}\right) \tag{2}\\ \end{align}$$

Denote $g(k) = f(k) - \frac{16}{7}4^k$, then $$(2)\Longleftrightarrow g(k) = 2g(k-1) +g(k-2) \tag{3}$$

$(3)$ is a well-know recurrent sequence, so it's easy to prove that

$$g(k) = Ax_1^k+Bx_2^k \tag{4}$$ with $(x_1, x_2) = ( 1 + \sqrt{2}, 1 - \sqrt{2})$ are two roots of the quadratic equation $x^2=2x+1$ and $A,B$ can be determined from the initial values of the sequence $g(k)$ (for example, $g(0)$ and $g(1)$).

Finally, we have

$$T(2^k) =f(k) =g(k)+\frac{16}{7}4^k = Ax_1^k+Bx_2^k + \frac{16}{7}4^k$$ or with $k = \ln(n) / \ln(2)$ $$\begin{align} T(n) &= Ax_1^\frac{\ln(n)}{\ln(2)}+Bx_2^\frac{\ln(n)}{\ln(2)} + \frac{16}{7}4^\frac{\ln(n)}{\ln(2)} \\ &=A n^\frac{\ln|x_1|}{\ln 2} + B n^\frac{\ln|x_2|}{\ln 2} + \frac{16}{7}n^2\tag{5}\\ \end{align} $$

We observe that $2 > \frac{\ln|x_1|}{\ln 2} > \frac{\ln|x_2|}{\ln 2}$, so the third term of $(5)$ is dominant for $n \longrightarrow + \infty$. Then

$$T(n) \sim \frac{16}{7}n^2 + \mathcal{o}(n^2)$$