1
$\begingroup$

I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step.

$T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ which then I got $T(n)=T(n-2)+2(n-1)+2n$. $T(n-2)$ gives $T(n-3)+2(n-3)$ which plugging it back in gives $T(n)=T(n-3)+2(n-3)+2(n-1)+2n$. I substituted the following $2(n-3)+2(n-1)+2n$ into a summation that gave me $\sum_{i=0}^k 2(n-i)$$=-(k+1)(k-2n)$. I am not too sure how I should continue.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

You're almost there. You correctly have $$\begin{align} T(n) &= T(n-1)+2n\\ &= [T(n-2)+2(n-1)] + 2n = T(n-2)+2(n-1)+2n\\ &= T(n-3)+2(n-2)+2(n-1)+2n\\ &= T(n-4)+2(n-3)+2(n-2)+2(n-1)+2n \end{align}$$ and in general, $$ T(n)=T(n-j)+2(n-j+1)+2(n-j+2)+2(n-j+3)+\dotsm+2n $$ Now all you need is the base value for the recurrence. Let's suppose that it was $T(0)=0$ (for the big-O estimate it really wouldn't matter if we had had, say $T(1)=3$ as our base).

To get to the base case, $T(0)$, we'd then need $n-j=0$. In that case, we'd have $$ T(n)=T(0)+2(1)+2(2)+2(3)+\dotsm+2n= \sum_{k=1}^n2k=2\cdot\frac{n(n+1)}{2} = O(n^2) $$

$\endgroup$
3
  • 3
    $\begingroup$ And, of course, prove that guess correct by induction. $\endgroup$
    – Raphael
    Jan 24, 2016 at 23:35
  • $\begingroup$ @Raphael. Of course. $\endgroup$ Jan 25, 2016 at 14:17
  • $\begingroup$ Some people seem to think it's not necessary (for a formal proof) so I have fallen into the habit of mentioning it. No offense intended. $\endgroup$
    – Raphael
    Jan 25, 2016 at 15:57
0
$\begingroup$

You need to find the value of $k$. What's the last possible value for $i$? If you substitute $n$ by $1$ in the original formula, what form does the term $2n$ take? You get $2*1$, which must equal $2(n-k)$. Thus, $k = n-1$.

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