[Math] How to solve $T(n)=4T(n/4)+n^2$ by recursion tree and master theroem

recurrence-relations

My solution is different between master thereom and recursion tree… How to solve it?


  1. Recursion Tree

In the problem, when n=1, T(n)=c (constant). So In recursion tree, I found pattern.

$4^0\frac{n^2}{4^0}, 4^1\frac{n^2}{4^1}, 4^2\frac{n^2}{4^2}…$

I got a height by this way.

$\frac{n^2}{4^x}=c$ , so, $x=\log_4 {n^2c^{-1}}=log_4 n^2 -log_4c$

From above height $x$,

$T(n)=\sum_{i=0}^{log_4 n^2}n^2=n^2(log_4 n^2 + 1)=n^2log_4n^2+n^2=2n^2log_4n+n^2=\theta(n^2log_4 n)$

  1. Master Theroem

a=4, b=4

$n^2=\Omega(n^{{log_4 4}+\epsilon})$ it is correct when $\epsilon=1$, $4\frac{n^2}{4^2}\le cn^2$ it is correct when $c\ge\frac{1}{4}$

$\therefore T(n)=\theta(f(n)=\theta(n^2)$


Why I get a different answer?

Best Answer

You missed power in the denominator.

$$T(n) = 4^0 \frac{n^2}{(4^0)^2}+4^1 \frac{n^2}{(4^1)^2}+4^2 \frac{n^2}{(4^2)^2}+\dots+4^{\log_{4}{n}} \frac{n^2}{{(4^{\log_{4}{n}})}^2}$$

So we have:

$$T(n) = n^2*(\sum_{i=0}^{\log_{4}{n}}{\frac{1}{4^i}})=\Theta(n^2)$$

Related Question