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?


1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .