[Solved]: Solution to recurrence $T(n) = T(n/2) + n^2$

Problem Detail: 

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) $?

Asked By : codeomnitrix

Answered By : Kaya

I believe you commit your error when you suggest $(1/4)^{\log_2 n}=1-4^{\log_2 n}$ when in fact you should make the substitution $(1/4)^{\log_2 n}=4^{-\log_2 n}$. If you continue your calculation with this instead it will not yield a $n^4$ term and the highest power of $n$ will remain 2 as desired.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19318