4.3-1

Show that the solution of T(n) = T(n - 1) + n is O(n2). If you try to prove $T(n) = cn^2$ you will end up with $$cn^2 - (-c+2nc-n)$$ to prove $(-c+2nc-n) \gt 0 $ will be difficult. But as you can see if you can eliminate c from above equation it will be easier to prove. let assume below $$T(n) = cn^2 - c$$ $$T(n) = cn^2 + c - 2nc +n -c $$ c will cancel out in above equation hence $$T(n) = cn^2 - (2nc-n)$$ $$2nc-n \geq 0 $$ $$2nc \geq n $$ $$c \geq 1/2 $$ $$ T(1) = \theta(1) \leq c $$ For base case if we take c should be sufficiently large like 100 the above eq will satisfy base case