Solve: T(n) = T(n-1) + n

algorithm, math, recurrence

Solution

I guess this is supposed to be induction?

So base case n=1 is trivial. Induction case, assume n>1. (*) Suppose T(n-1) is O((n-1)2)=O(n2). Show that T(n) is also O(n2).

 T(n) = T(n-1) + n
      < c (n-1)^2 + n,  assume c>1 wlog
      < c n^2 - 2cn + c + n
      < c n^2 - (2c - 1)n + c
      < c n^2

for n > 1, c > 1.

Here is the break out:

First, notice that when c > 1, 2c - 1 > c, so you have

      < c n^2 - (2c - 1)n + c
      < c n^2 - (c)n + c

Next, notice that when n > 1, -(c)n+c = (1-n) c < 0, so you have

      < c n^2 - (c)n + c
      < c n^2

Since there is a constant c such that T(n) < c n^2, clearly T(n) is O(n2).

Is that roughly along the line of what you want? Had to edit it a bunch of times to fix edge cases.

Problem

In Cormen's Introduction to Algorithm's book, I'm attempting to work the following problem: Show that the solution to the recurrence relation T(n) = T(n-1) + n is O(n2 ) using substitution (There wasn't an initial condition given, this is the full text of the problem) However, I can't seem to find out the correct process. The textbook only briefly touches on it, and most sites I've searched seem to assume I already know how. If someone could give me a simple, step by step guide, or even a link to one, I would appreciate it. For kicks, here's my attempt so far: T(n) <= c(n^2) <= c(n-1)^2 + n <= c(n^2 -2n +1) + n (which I'm pretty sure is not < c(n^2)) Thanks again. UPDATE: Here's an example of the method I'm trying to accomplish, to avoid confusion. Prove the solution is O(nlog(n)) T(n) = 2T([n/2]) + n The substitution method requires us to prove that T(n) <= cn*lg(n) for a choice of constant c > 0. Assume this bound holds for all positive m < n, where m = [n/2], yielding T([n/2]) <= c[n/2]*lg([n/2]). Substituting this into the recurrence yields the following: T(n) <= 2(c[n/2]*lg([n/2])) + n <= cn*lg(n/2) + n = cn*lg(n) - cn*lg(2) + n = cn*lg(n) - cn + n <= cn*lg(n) where the last step holds as long as c >= 1 I can follow this logic just fine, but when I attempt to duplicate the steps in the problem above, I get stuck.

Original source

Related problems