# Wby can't this recurrence be solved by direct guessing?

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

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

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

-

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

-