Find $a$ such that $T(n)=T(\frac{n}2)+aT(\frac{n}4)+n^2$ is solved by $T(n)=\omega(n^2)$

Question

i have the following question:

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

For which value of a, if exists, does $T(n)=\omega(n^2)?$ In that case, what's the asymptotic function of $T(n)$?

I've tried to open this function with a recursion tree and repeated positioning (like: $T(n)=n^2+[T(\frac{n}4)+aT(\frac{n}8)+\frac{n^2}4]+a[T(\frac{n}8)+T(\frac{n}{16})+\frac{n^2}{16}]=...$ and so on, but it doesn't get me anywhere. Can anyone help?

Answer 1

Hint

For $n=2^k$ you can write down the following:

$$T(2^k) = T(2^{k-1}) + aT(2^{k-2}) + 2^{2k}$$

Substituting $f(k) = T(2^{k})$:

$$f(k) = f(k-1)+af(k-2) + 2^{2k}$$

This is a simple linear inhomogeneous relation. To deal with it, you solve homogeneous relation and then try to find a particular solution to this equation (most likely in the form $r2^{bk}$). Having in hand $f(k)$, it is easy to estimate the asymptotic behavior of $T(n)$ depending on $a$.