Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What makes you think we will be able to guess which theorem you assigned the number $1$ to? –  joriki Dec 12 '11 at 14:06
    
@joriki Sorry about that, I edited the question now. –  Jeune Dec 12 '11 at 14:18
add comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  Jeune Dec 12 '11 at 14:24
    
Sure, but then you only obtain $T(n)\le cn^2+n$, which is not in contradiction with $T(n) \le cn^2$. –  Peteris Dec 12 '11 at 14:28
add comment

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

share|improve this answer
    
And I would not use contradiction in the title, if I were you. –  Did Dec 12 '11 at 14:47
    
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}$)? –  Jeune Dec 12 '11 at 15:22
1  
Certainly not. See edit. –  Did Dec 12 '11 at 15:35
    
+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. –  Jeune Dec 12 '11 at 16:17
    
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$. –  Did Dec 12 '11 at 17:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.