# Solving a simple recurrence.

This isn't a homework question, but it is a problem in my textbook.

Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$

My approach:

Given $T(n) = T(n-1)$

Need to show $T(n) = cn^2$, where $c > 0$

Substitute:

$\begin{eqnarray*} T(n) & \le & c(n^2 - 1) + n^2\\ & \le & cn^2 - c + n^2\\ & \le & cn^2 + n^2 - c\\ & \le & n^2(c+1) - c\\ & \le & O(n^2) \end{eqnarray*}$

Is this the correct approach? Assuming there will be some constant that provides an upper bound.

-
I think in this particular case the easiest method would be to solve for $T(n)=1+2+\cdots+n=\cdots$ and show that it is $O(n^2)$. – wj32 Nov 3 '12 at 22:12
Am I on the right track for the substitution method? – The Internet Nov 3 '12 at 22:21
Your "need to show" and "substitute" parts are a bit mystifying.... Where did the $m$ come from? Why that substitution? Remember you want $T(n)=O(n^2)$, not $T(n^2)=O(n^2)$. – Cameron Buie Nov 3 '12 at 22:25
The m was from the last recurrence I solved, should have removed it. The need to show step comes from the definition of big O, that the function T(n) has an upper bound given a constant c multiplied by n. The confusion comes from when I attempt to substitute. – The Internet Nov 3 '12 at 22:33

My approach would be simply to solve the recurrence: it’s not hard to see and to prove by induction that $$T(n)=T(0)+\sum_{k=1}^nk=T(0)+\frac{n(n+1)}2=\frac12n^2+\frac12n+T(0)\;,$$ and one can then appeal to the standard result that a polynomial of degree $k$ is $O(n^k)$. If you don’t have that result available, let $C=\max\left\{\frac12,|T(0)|\right\}$, and note that

$$|T(n)|=\left|\frac12n^2+\frac12n+T(0)\right|\le C(n^2+n+1)\le 3Cn^2$$

for $n\ge 1$.

I don’t follow your approach. If I were to do something along those lines, I’d assume that $T(k)\le ck^2$ for $k<n$. Then

\begin{align*} T(n)&=T(n-1)+n\\ &\le c(n-1)^2+n\\ &=cn^2-2cn+1+n\\ &=cn^2-(2cn-n-1)\\ &=cn^2-\big((2c-1)n-1\big)\;. \end{align*}

You want to be sure that $T(n)\le cn^2$, so you want to be sure that $(2c-1)n-1\ge 0$. This will be the case provided that $$c\ge\frac12\left(\frac1n+1\right)\;.\tag{1}$$ The righthand side of $(1)$ is a decreasing function of $n$, so its maximum value is $1$, when $n=1$. Thus, there are two constraints on $c$: it must be at least $1$ to ensure that $(2c-1)n-1\ge 0$ for all $n\ge 0$, and it must be big enough so that $T(1)\le c$. Taking $c=\max\{1,|T(1)|\}$ does the job.

-
I see you're right. The closed form on the summation is the route I should have taken. But in theory, if I wanted to solve by substitution am I on the right track? – The Internet Nov 3 '12 at 22:16
@Dave: I honestly can’t figure out how your calculation is supposed to show that $T(n)$ is $O(n^2)$; I’ve expanded my answer to include a calculation that would do what you want. – Brian M. Scott Nov 3 '12 at 22:27

To prove that $T(n) = T(n-1) + n$ is $O(n^2)$ we just need to show that there's some scaling constant $c$ and some point $N$ such that for all $n>N,$ $T(n) < c n^2$.

We could do this by induction: If $T(n-1) < c n^2$ then $T(n) = T(n-1) + n < c n^2 + 2 c n + c$ as long as $c \ge 1/2$, and this happens for every $n > 0$ (given that $c > T(0)$) so we've proved that $T(n)$ is $O(n^2)$ by the pair $c=1/2+|T(0)|,N=0$.

-

Let's suppose we're starting with $n=0$. I claim that for all $n\ge 0$ we have $$T(n)=T(0)+\frac{n^2+n}2.$$

For $n=0$, this holds trivially by substitution. Suppose that it holds for some $n$. Then by our recurrence relation and the hypothesis, $$T(n+1)=T(n)+n+1=T(0)+\frac{n^2+n}2+\frac{2n+2}2=T(0)+\frac{n^2+2n+1}2+\frac{n+1}2=T(0)+\frac{(n+1)^2}2+\frac{n+1}2=T(0)+\frac{(n+1)^2+(n+1)}2,$$ so the claim holds by induction. Can you get the rest of the way from there?

-

Let us think of our sequence as $T(1), T(2), T(3), \dots$. I think you are trying to prove by induction that there is a $c$ such that $T(n)\lt cn^2$ for all $n$. There certainly is a $d$ such that $T(1)\lt d(1^2)$. Let $c=\max(d,1)$.

Assume by way of induction hypothesis that $T(n-1)\lt c(n-1)^2$. Then $$T(n)=T(n-1)+n\lt c(n-1)^2+n =cn^2-2cn+n+1.$$ But $c\ge 1$, and therefore $-2cn+n+1\le -2n+n+1=1-n\le 0$, and therefore $$T(n)\lt cn^2.$$

-