0
$\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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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