(Avoiding pitfalls) I was reading solution to 4.3.5 when I came across this error. In the line prior to the end, when proving that T(n) is O(nlgn), 2c was omitted. but doing so would mean c < 0 which is not correct. In other words induction hypothesis doesn't hold for the proof to be correct. adding -2c to induction hypothesis resolves the issue. same thing Omega.
walkccc
commented
2 years ago
(Avoiding pitfalls) I was reading solution to 4.3.5 when I came across this error. In the line prior to the end, when proving that T(n) is O(nlgn), 2c was omitted. but doing so would mean c < 0 which is not correct. In other words induction hypothesis doesn't hold for the proof to be correct. adding -2c to induction hypothesis resolves the issue. same thing Omega.