Show that $S(m)=\Theta(m^2)$ with Recurrence Relation

[evinda]

Hello! (Smile)

Let $S(m)=S(m-1)+m$.
I want to show that $S(m)=\Theta(m^2)$.

That's what I have tried:

We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that :
$$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$

We will show that $c_1 m^2 \leq S(m) \leq c_2 m^2$.

$$S(m)=S(m-1)+m \leq c_2(m-1)^2+m=c_2 m^2-2c_2 m +c_2+m=c_2m^2-(2c_2m-c_2-m) \leq c_2 m^2, \text{ if } 2c_2m-c_2-m \geq 0 \Rightarrow c_2(2m-1) \geq m \Rightarrow c_2 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_2 \geq \frac{1}{2}$$

So, we have that $S(m)=O(m^2)$.

$$S(m)=S(m-1)+m \geq c_1(m-1)^2+m=c_1 m^2-2c_1 m +c_1+m=c_1m^2-(2c_1m-c_1-m) \geq c_1 m^2, \text{ if } 2c_1m-c_1-m \leq 0 \Rightarrow c_1(2m-1) \geq m \Rightarrow c_1 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_1 \geq \frac{1}{2}$$

So, we have that $S(m)=\Omega(m^2)$.

Therefore, $S(m)=\Theta(m^2)$.

Could you tell me if it is right or if I have done something wrong? (Thinking)

Also, can we find from the above the exact solution of the recurrence relation, or do we have to do it in an other way, like using the substitution method? If so, how can we know when the recursion ends, without having an initial condition?

 

[chisigma]

Hello! (Smile)

Let $S(m)=S(m-1)+m$.
I want to show that $S(m)=\Theta(m^2)$.

That's what I have tried:

We suppose a positive integer $m>0$. We suppose that $S(m-1)=\Theta((m-1)^2)$, so it holds that $\exists c_1, c_2>0$ such that :
$$c_1 (m-1)^2 \leq S(m-1) \leq c_2(m-1)^2$$

We will show that $c_1 m^2 \leq S(m) \leq c_2 m^2$.

$$S(m)=S(m-1)+m \leq c_2(m-1)^2+m=c_2 m^2-2c_2 m +c_2+m=c_2m^2-(2c_2m-c_2-m) \leq c_2 m^2, \text{ if } 2c_2m-c_2-m \geq 0 \Rightarrow c_2(2m-1) \geq m \Rightarrow c_2 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_2 \geq \frac{1}{2}$$

So, we have that $S(m)=O(m^2)$.

$$S(m)=S(m-1)+m \geq c_1(m-1)^2+m=c_1 m^2-2c_1 m +c_1+m=c_1m^2-(2c_1m-c_1-m) \geq c_1 m^2, \text{ if } 2c_1m-c_1-m \leq 0 \Rightarrow c_1(2m-1) \geq m \Rightarrow c_1 \geq \frac{m}{2m-1} \to \frac{1}{2} \Rightarrow c_1 \geq \frac{1}{2}$$

So, we have that $S(m)=\Omega(m^2)$.

Therefore, $S(m)=\Theta(m^2)$.

Could you tell me if it is right or if I have done something wrong? (Thinking)

Also, can we find from the above the exact solution of the recurrence relation, or do we have to do it in an other way, like using the substitution method? If so, how can we know when the recursion ends, without having an initial condition?

Writing the equation in slightly different form You have...

$\displaystyle s_{n+1} = s_{n} + n + 1\ (1)$

Setting $s_{0}$ the value of the $s_{n}$ for n=0, the solution of (1) is...

$\displaystyle s_{n} = s_{0} + \sum_{k=1}^{n} k = s_{0} + \frac{n\ (n+1)}{2}\ (2)$

... so that is $\displaystyle s_{n} = \mathcal{O} (n^{2})$...

Kind regards

$\chi$ $\sigma$

 

[evinda]

Writing the equation in slightly different form You have...

$\displaystyle s_{n+1} = s_{n} + n + 1\ (1)$

Setting $s_{0}$ the value of the $s_{n}$ for n=0, the solution of (1) is...

$\displaystyle s_{n} = s_{0} + \sum_{k=1}^{n} k = s_{0} + \frac{n\ (n+1)}{2}\ (2)$

... so that is $\displaystyle s_{n} = \mathcal{O} (n^{2})$...

Kind regards

$\chi$ $\sigma$

I see.. But is the way I showed that $S(m)=\Theta(m^2)$ also right?
Or have I done something wrong?