My solution is different between master thereom and recursion tree... How to solve it?
- 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)$
- 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?
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)$$