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'm reading Introduction to Algorithms by Cormen et. al. and in a part there, they say that this recurrence :

T(n)=T(n/2) + T(n/2) + 1

can't be proved by the guessing method, were you just look at the recurrence and guess that T(n)=O(n) because, when you do that, and to prove it you plug the answer in, you get

T(n) <= c*(n/2) + c*(n/2) + 1
=c*n + 1

And they say that this is NOT Big-Oh(n)

I want to know why? I though that with the asymptotic notations, you can just eliminate constants like +1 and get the answer.

But they say that here T(n) = c*n + 1 doesn't imply that

T(n) <= c*n for any value of c.

How is this justified? I though that it did imply that..

share|improve this question
    
In fact, this is only defined for $n$ a power of $2. \ \ T(2^n)=2^{n+1}-1=2*(2^n)-1$, so it is $O(n)$ –  Ross Millikan Oct 13 '12 at 4:06
4  
The guessing method can solve any problem. You just have to be very very good at it! –  Mariano Suárez-Alvarez Oct 13 '12 at 4:20
    
What you can prove by induction, is $T(n)\le cn-1$. To be precise, one should be more specific about the interpretation of $\frac n2$ for odd $n$. –  Hagen von Eitzen Oct 13 '12 at 7:03
add comment

2 Answers

up vote 1 down vote accepted

The problem is that the hypothesis that $$T\left(\frac{n}2\right)\le cn\tag{1}$$ doesn’t justify the conclusion that $T(n)\le cn$: the recurrence gives you only that

$$T(n)\le c\left(\frac{n}2\right)+c\left(\frac{n}2\right)+1=cn+1\;.$$

This means that you might need a larger constant multiplier for $n$ than the $c$ that was sufficient for $\frac{n}2$. But in order to claim that $T(n)$ is $O(n)$, you must show that there is a constant $c>0$ such that $T(n)\le cn$ for all sufficiently large $n$, and you haven’t done that.

With the recurrence $$T(n)=2T\left(\frac{n}2\right)$$ you can do this: if you assume that $(1)$, this recurrence implies that $T(n)\le cn$ with the same constant $c$.

share|improve this answer
add comment

Every time you divide the size of the problem by a factor of two you get extra 1. If you continue rewriting the problem in a smaller terms you will get $\log n$ such ones. That is why you cannot neglect this term. As for your proof, here is mistake, your claim is $T(k)\leq c*k$. Initial recurrence $$T(n)=2T(\frac{n}{2})+1$$ Pluging in your solution gives: $$T(n)=2T(\frac{n} {2} )+1\leq 2(c \frac{n}{2})+1=cn+1\ne cn$$ However solution $O(n)$ is correct, but you need to derive it in a different way: assume $T(k)=ck-b$ for some $c,b>0$ which will be determined later $$T(n)=2T(\frac{n} {2} )+1\leq 2(c\frac{n}{2}-b)+1=cn-(2b-1)\leq cn$$ if $b\geq \frac{1}{2},c>0$.

share|improve this answer
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.