walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.63k stars 1.26k forks source link

Is solution to exercise 4.3.6 wrong ? #457

Open RyanTalbi opened 2 years ago

RyanTalbi commented 2 years ago

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