0
$\begingroup$

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

  • 0
    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$.2012-10-13

2 Answers 2

1

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

1

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