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$
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
    $\begingroup$ And, of course, prove that guess correct by induction. $\endgroup$ – Raphael Jan 24 '16 at 23:35
  • $\begingroup$ @Raphael. Of course. $\endgroup$ – Rick Decker Jan 25 '16 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 '16 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, privacy policy and cookie policy

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