What is the value of following recurrence? T(n) = T(n/4) + T(n/2) + cn2 T(1) = c T(0) = 0 Where c is a…

The recurrence solves to $O(n^2)$. In the recursion tree, the root contributes $cn^2$, the next level contributes $c(n/4)^2 + c(n/2)^2$ $= \frac{5}{16}cn^2$, and level $k$ contributes at most $\left(\frac{5}{16}\right)^k cn^2$. Since this is a decreasing geometric series with ratio $5/16 < 1$, the total work is bounded by $cn^2 \sum_{k=0}^{\infty} (5/16)^k$ $= \frac{16}{11}cn^2$ $= O(n^2)$.