I am studying algorithms and I came across this problem:
$t(1) = 1$ and $t(n) = 4t(n/2) + n^2$
Calculate the exact value of $t(n)$ for all $n=2^l, l \in N $
Initially I thought this would be a master theorem problem, but how would I go on to find the exact value of a recursion equation?
We can rewrite the recurrence: $$ T(2^\ell) = 4T(2^{\ell-1})+ 4^\ell,\ \ T(2^0)=1. $$
Computing the first few values, we have: \begin{align} T(2^0) &= T(1) = 1\\ T(2^1) &= 4T(2^0) + 4^1 = 4\cdot1 + 4 = 8\\ T(2^2) &= 4T(2^1) + 4^2 = 4\cdot 8 + 16 = 48\\ T(2^3) &= 4(2^2) + 4^3 = 4\cdot 48 + 64 = 256. \end{align}
This suggests the pattern $T(2^\ell) = 4^\ell(1+\ell)$. Indeed, $T(2^0) = 4^0(1+0) = 1$, and if $T(2^\ell) = 4^\ell(1+\ell)$ for some $\ell\geqslant 0$ then $$ T(2^{\ell+1}) = 4T(2^{\ell}) + 4^\ell = 4^\ell(2+\ell), $$ so by induction this expression holds for all nonnegative integers $\ell$.