Is solution to exercise 4.3.8 wrong ?

[RyanTalbi]

In the second part, we start by guessing $T(n) <= cn²-cn$ then we find $T(n) <= cn²$ and conclude that $T(n) = O(n²)$ in my view, this is wrong referring to the c) of the substitution method chapter which clearly indicate that in this case you need to prove $T(n) <= cn²-cn$ and that the fact that $T(n) <= cn²$ is not enough ( we don't have $cn2 <= cn²-cn$ so we cannot conclude that $T(n) <= cn²-cn$ ).

Here is the solution that I do propose :

Let's put $T(n) <= cn²-f(n)$ where f is a function of N in N.

We have $T(n) <= 4(c(n/2)²-f(n/2))+n² = 2cn²-4f(n/2)+n²$. We want to have $$-4f(n/2)+n² <= -f(n) ≡ 4f(n/2)-n² >= f(n)$$
Let's write the recurrence equation $g(n) = 4g(n/2)-n²$ and try $g(n) <= c'nlg(n)$ c' being a constant > 0

We then have $g(n) <= 4c'(n/2)lg(n/2)-n² = 2c'nlg(n/2)-n² = n(2c'lg(n/2)-1/2n)$ And then I concluded by saying that we know we have $2c'lg(n/2) = o(n)$, by definition this does means that for any constant r > 0, there is a rank n0 from which $r*n > 2c'lg(n/2)$ so $2c'lg(n/2)-1/2n$ will end by becoming lower than 0 and since n is positive $n(2c'lg(n/2)-1/2n)$ will end by becoming lower than 0 for any possible c' > 0 from a certain rank. As $c'nlg(n)$ will never be lower than 0 I conclude that $g(n) <= c'nlg(n)$ starting from a certain rank.
We need to verify the base's cases. We can't verify for g(1) because we have $c'1lg(1) = 0$ which cant be greater than g(1) but we can easily verify it for g(2) and g(3) with $g(2) = 2c'$ and $g3 = 3c'lg(3)$ g(2) can be verified for any $c' >= g(2)$ and g(3) can be verified for any $c' => g(3)$ so we take $c' = max(g(2),g(3))$.

The recurrence hypothesis is verified. The base's cases are verified so the solution is valid.

So $c'nlg(n)$ is a solution to this "sub-recurrence", and we can take $f(n) = c'nlg(n)$