clrs4e-solutions
clrs4e-solutions copied to clipboard
4.7-3
Reopening, because the errata now states that the function f should be asymptotically positive (the bug it fixes is in the notation f(n) \ge 0 that should now say f(n) > 0).
The statement is flawed even after applying the fix from the errata, since the polynomial-growth in fact implies asymptotic nonnegativity of the function, not only asymptotic positivity.
I have sent this bug to the Authors and am waiting for their reply.
No response from the Authors, so I am retaining the clarification in the solution for now, after slightly rewording it.