I am working with the equation
$T(n) = T(n/2) + n^2$, given $T(1) = 0$.
I started by using backwards substitution arriving at
$T( ( ( n - 1 ) / 2 ) + ( n - 1 ) ^ 2 ) + n ^ 2$ and eventually arrived at
$T( ( n - k ) / 2 )$ + the summation of $(n-i)^2$ from $i = 0...k$. However, I am not sure where to go from here because using $T(1) = 0$ would give $0/2$ plus the summation which gives $0$.
This does not seem like it would work for $n = 1$.
Any suggestions?
On
Let n=$2^k$ for some k. Then we have $$T(2^k)=T(2^{k-1})+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-2})+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=T(2^{k-3})+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ and so on till we get $$T(2^k)=T(2^0)+2^{2(k-(k-1))}+...+2^{2(k-2)}+2^{2(k-1)}+2^{2k}$$ $$\Rightarrow T(2^k)=\sum_{i=0}^{k-1} 2^{2(k-i)}$$ $$\Rightarrow T(2^k)=4\cdot\frac{4^{k}-1}{3}$$
Substituting the value of $2^k=n$ we get $$T(n)=\frac 43\cdot (n^2-1)$$
Use the substitution $n = 2^k$, $t(k) = T(2^k)$:
$\begin{align} t(k) = t(k - 1) + 2^{2 k} \end{align}$
This linear recurrence is easy to solve (or just write it as $t(k) - t(k - 1) = 2^{2 k}$ and sum over $k$).