1
$\begingroup$

I am trying to solve the recurrence

$T(n) = 4 T \Big( \frac{n}{2} \Big) + n .$

using the master method and got $\Theta(n^2)$ using the first case theorem:

If $f(n) = O(n^{\log_{b}a-\epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta \left(n^{\log_b a} \right)$.

However when I verify the upper bound using the substitution method it seems I arrive at a contradiction:

After assuming that $T \left( \frac{n}{2} \right) \leq c(\frac{n}{2})^{2}$ and then substituting I get

$ \begin{align*} T(n) &= 4c \left( \frac{n}{2} \right)^2 + n \\ T(n) &= 4c \cdot \frac{n^2}{4} + n \\ T(n) &= cn^{2}+ n \leq cn^2 , \end{align*} $ which is obviously a contradiction.

Obviously there is something I am not seeing here or overlooked. Would like to have it pointed out.

  • 0
    @joriki Sorry about that, I edited the question now.2011-12-12

2 Answers 2

2

You are assuming $T(\frac{n}{2})=c(\frac{n}{2})^2$ and trying to prove $T(n) \le cn^2$.

Instead, you can only obtain that $T(n)=4T(\frac{n}{2})+n \le cn^2+n$, which does not contradict anything.

Hint. To actually prove this, you might want to try a different inductive hypothesis, perhaps a quadratic polynomial in $n$.

  • 0
    Sure, but then you only obtain $T(n)\le cn^2+n$, which is not in contradiction with $T(n) \le cn^2$.2011-12-12
2

If $H_k$ is the hypothesis that $T(2^k)=c4^k-2^k$, then, for every $k\geqslant0$, $H_k$ implies $H_{k+1}$. Since $H_0$ holds for $c_T=T(1)+1$, this proves that, for every $k\geqslant0$, $ T(2^k)=c_T4^k-2^k. $ To deal with indices which are not powers of $2$, one must assume the following:

The sequence $(T(n))_n$ is nondecreasing.

Then, for every $n\geqslant1$, there exists $k$ such that $2^k\leqslant n\lt2^{k+1}$, hence $ T(n)\leqslant T(2^{k+1})= c_T4^{k+1}-2^{k+1}\leqslant4c_T4^{k}\leqslant4c_Tn^2. $ Likewise, $4^k\gt\frac14n^2$ and $2^k\leqslant n$ hence $ T(n)\geqslant T(2^k)=c_T4^k-2^k\geqslant\tfrac14c_Tn^2-n. $ Finally, for every $n\geqslant1$, $ \tfrac14c_T^2n^2-n\leqslant T(n)\leqslant4c_Tn^2, $ and $n=o(n^2)$, hence $T(n)=\Theta(n^2)$.

  • 0
    Since one relates $T(n)$ to $T(2n)$, the fact that the powers of $2$ enter the picture is not very surprising, I would say. Likewise, one could consider $(T(3\cdot2^k))_{k\geqslant0}$ or $(T(5\cdot2^k))_{k\geqslant0}$, and so on. But there is no way to get a relation between $T(1)$ and $T(3)$, for example, which is why I added the hypothesis that $(T(n))_{n\geqslant1}$ is nondecreasing. Otherwise, one is stuck with different problems, each concerning a sequence $(T((2i+1)\cdot2^k))_{k\geqslant0}$, for some $i\geqslant0$.2011-12-12