0
$\begingroup$

I see this in CLRS:

We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence $T(n)=2T(\lfloor n/2\rfloor)+ n$. We guess that the solution is $O(n\lg n).$ The substitution method requires us to prove that $T(n)<=cn \lg n$ for an appropriate choice of the constant c>0.

And next :

With T(1)=1, we derive from the recurrence that T(2)=4 and T(3)=5. Now we can complete the inductive proof that $T(n) <= cn \lg n$ for some constant $c>1$ by choosing $c$ large enough so that $T(2)<=c_2 \lg 2$ and $T(3)<= c_3 \lg 3$. As it turns out, any choice of $c >= 2$ suffices for the base cases of $n >= 2$ and $n >= 3$ to hold.

So question is why we can change $c$? Should constant be fixed for using mathematical induction? (There is also quantifier $\exists \ c: f(n)<=cg(n)\ \forall n >= n_0$ in definition of $O$) Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

It's not being changed. The author is looking at the base cases to see for which constant $c$ the proof will work. The formulation "Now we can complete the inductive proof [...] for some constant $c$" is a bit sloppy; I can see how you may have thought that the proof was started, then $c$ was chosen, and then the proof was completed; but that's not what is meant. Once $c$ is chosen such that the base cases work out, you can do the entire proof with that fixed value of $c$, from start to finish.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .