- #1
evinda
Gold Member
MHB
- 3,741
- 0
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?
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?