1
$\begingroup$

How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method? I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$: $$T(n) \leq O(n^2) \\ \leq c(n-1)^2+n \\ \leq cn^2+c-2cn+n$$ How can i continue?

$\endgroup$

3 Answers 3

0
$\begingroup$

We can prove easily in induction, that $T(n)=c + \sum_{i=1}^n i$. Assume correctness for $n$, we will prove for $n+1$. Clearly, $T(n+1)=T(n)+(n+1)=c + n+1 + \sum_{i=1}^n i = c + \sum_{i=1}^{n+1} i$.

A nice result you are probably familiar with, if you learned about arithmetic progression series, is that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$

Thus, $T(n) = c + \frac{n(n+1)}{2} = \Theta(n^2)$

$\endgroup$
0
$\begingroup$

$$T(n)=T(n-1)+n=\\=T(n-2)+(n-1)+n=\\=\cdots=\\ =T(1)+2+\cdots+(n-1)+n =\\= T(1) + \frac{n(n+1)}{2}-1 \in \Theta(n^2)$$

$\endgroup$
0
$\begingroup$

c + n - 2cn is always negative for c , n >1 so T(n) < cn2

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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