Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer

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?

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.