Solution to recurrence $T(n) = T(n/2) + n^2$ I am getting confused with the solution to this recurrence - 
$T(n) = T(n/2) + n^2$

Recursion tree - 

T(n)                      Height lg n + 1
 |
T(n/2)
 |
T(n/4)


So it turns out to be -

$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log_2 n - 1})$

$T(n) = 4*n^2(1- (1/4)^{\log_2 n})/3 + n^2 $

$T(n) = 4*n^2(1 - 1^{\log_2 n} + 4^{\log_2 n})/3 + n^2 $

$ T(n) = 4*n^2(1 - 1 + n^{\log_2 4})/3 + n^2$

$ T(n) = 4*n^2(n^2)/3 + n^2$

$ T(n) = 4/3 * (n^4) + n^2 $

$ T(n) = \Theta(n^4) $

But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?
Try this way:
$$
\begin{align*}
T(n) &amp;= T(n/2) + n^2 \\
T(n) &amp;= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &amp;= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$

You will end up with:
$$
\begin{align*}
T(n) &amp;= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &amp;= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots
\end{align*}
$$

We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.

Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c_1f(n)$ and a lower bound of $T(n) \ge c_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.