CLRS
CLRS copied to clipboard
Is solution to exercise 4.3.6 wrong ?
I think there is a major error in the solution for the exercise 4.3.6. We pass from $$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$ assuming c > 1 but we then pass from this to $$T(n) <= c(n-a)lg(n-a)$$ assuming a >= 34 but if a >= 34 then the previous step is not valid, if we have a >= 34 and c > 1 then we do have $c(n+34-2a) = c*n$ so we do not have $-c(n+34-2a)+n < 0$ so we can't pass from $$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$.