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
    What makes you think we will be able to guess which theorem you assigned the number $1$ to?2011-12-12
  • 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
    Of course I have to assume first that T($\frac{n}{2}$) $\leq$ c$(\frac{n}{2})^{2}$. Isn't that how the induction works first?2011-12-12
  • 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
    And I would not use *contradiction* in the title, if I were you.2011-12-12
  • 0
    If I use the H(n) you gave as a hypotheses I get T(n) $\leq$ (c-1)$n^{2}$ + n. How can I now say that T(n) = O($n^{2}$)?2011-12-12
  • 1
    Certainly not. See edit.2011-12-12
  • 0
    +1 that's an interesting answer. It makes sense to me that T(n) $\leq$ $c_{1}$ $n^{2}$ -n $\leq$ $c_{1}$ $n^{2}$. However I do not understand how $2^{k}$ suddenly came into the picture.2011-12-12
  • 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