I m trying to find the time complexity of the following equation:
$$ T(n) = 2 T(n/2) + n^2 $$
I understand that you need to find patterns - so i got this:
$$ 2^2 T(n/2^2) + n^2/2 + n^2 $$ $$ 2^3 T(n/2^3) + n^2/2^2 + n^2/2 + n^2 $$
I don't understand what comes after this- Does this involve using summation of AP/GP?
Any help will be much appreciated.
If you want to spot a pattern, you should probably start with $n=2^k$ (anyway it's better so that $T(n2^{-i})$ makes sense).
$$\begin{align} T(2^k) &= 2T(2^{k-1})+2^{2k}\\ &= 4T(2^{k-2})+2^{2k-1}+2^{2k}\\ &=8T(2^{k-3})+2^{2k-2}+2^{2k-1}+2^{2k} \end{align}$$
Now you should be able to guess the pattern. It involves the computation of the sum of a geometric series.