What will be the complexity of $T(n) =T(n/4) +T(n/2) +n^2?$

Question

I need to solve this using the substitution method where you assume a solution and prove it using induction. Help.

Answer 1

The Ansatz $T(n)=cn^p$ gives $cn^p(1-1/4^p-1/2^p)=n^2$ so $p=2,\,c=\frac{1}{1-1/16-1/4}=\frac{16}{11}$. You're welcome to further investigate the asymptotic behaviour of$$U(n):=\frac{11T(n)}{16n^2}=\frac{11(T(n/4)+T(n/2)+n^2)}{16n^2}=\frac{U(n/4)}{16}+\frac{U(n/2)}{4}+\frac{11}{16},$$to motivate $U(n)\to1$ as $n\to\infty$. Certainly, if a finite $L:=\lim_{n\to\infty}U(n)$ exists then $L=\frac{5L+11}{16}\implies L=1$.