We can solve this using substitution method.
Claim: T(n) <= c n^2
IH: We assume that claim is true for all values of n < m.
Inductive Step: T(m) = T(m/4) + T(3m/4) + m^2
<= cm^2/16 + c 9 m^2 / 16 + m^2
= cm^2 (1/16 + 9/16 + 1/c)
= c m^2 (10/16 + 1/c)
<= c m^2 as long as 1/c <= 6/16. So, we can choose a value of c >= 16/6 and the rest of the math holds up.
QED.
Therefore, by PMI, T(n) <= c n^2, that is, T(n) = O(n^2).
Alternative Proof:
Follow the same logic, but instead of c, use a larger constant such as 10.
T(n) = 10 n^2/16 + 10 9n^2/16 + n^2.
<= 10 n^2.
| Presentations on Slideshare | Lecture Notes, etc