Solving a simple recurrence.

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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?

Answer 4

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.$$