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

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?

• What are the two solutions? How do you get yours? Commented Mar 29, 2018 at 2:31
• I edited now. plz see Commented Mar 29, 2018 at 3:53
• Re-posted on SO: stackoverflow.com/q/49548375/781723. Please do not re-post your question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Commented May 1, 2018 at 5:20

$$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}$$
$$T(n) = n^2*(\sum_{i=0}^{\log_{4}{n}}{\frac{1}{4^i}})=\Theta(n^2)$$