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