I have a question regarding section 4.3 in CLRS, in which the following is written:
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(n/2)+n. We guess that the solution is O(nlgn). The substitution method requires us to prove that T(n)<=cnlgn for an appropriate choice of the constant c>0.
The proof of the inductive step is:
$ T(n) ≤ 2(c \frac{n}{2} lg (\frac{n}{2})) + n$ $≤cn lg(\frac{n}{2}) + n$ $= cn lg n - cn lg 2 + n$ $= cn lg n - cn + n$ $≤cn lg n,$ where the last step holds as long as c >= 1
I omitted the floor notation since it's irrelevant to my question.
My question:
As far as I understand, because of the inductive hypothesis for n/2, there is a constant c that satisfies $ T(\frac{n}{2})<= c\frac{n}{2} lg (\frac{n}{2})$ (for n>=n0).
So, shouldn't the inductive step hold for the maximum between the specific constant c mentioned above corresponding to the function $T(\frac{n}{2})$, and 1, meaning max{c, 1}?
Thanks in advance!