Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) =T(n/2) +n^2.

Question

I am quite confused on this one, found this while going through a book. The book also says that it can be verified using substitution. I have no idea how to approach this one since I am quite new to algorithms. Any help would be appreciated.

Answer 1

Just keep substituting and see what appears.

$\begin{array}\\ t(n) &=t(n/2)+n^2\\ &=t(n/4)+(n/2)^2+n^2\\ &=t(n/4)+(1+1/2^2)n^2\\ &=t(n/8)+(n/4)^2+(1+1/2^2)n^2\\ &=t(n/8)+(1+1/2^2+1/4^2)n^2\\ &=t(n/16)+(n/8)^2+(1+1/2^2+1/4^2)n^2\\ &=t(n/16)+(1+1/2^2+1/4^2+1/8^2)n^2\\ \end{array} $

It looks like

$\begin{array}\\ t(n) &=t(n/2^k)+n^2\sum_{j=0}^{k-1}1/2^{2j}\\ &=t(n/2^k)+n^2\sum_{j=0}^{k-1}1/4^{j}\\ &=t(n/2^k)+n^2\dfrac{1-1/4^k}{1-1/4}\\ &=t(n/2^k)+n^2\dfrac{4(1-1/4^k)}{3}\\ &<t(n/2^k)+\dfrac43 n^2\\ \end{array} $