Need help in understanding the procedure of expanding recurrence formula

Asked Jan 27 '15 at 16:26

Active Jan 27 '15 at 16:26

Viewed 26 times

So here is the actual expansion:

\begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) + n \\ &= T(0) + \frac{n(n+1)}{2} = O(n^2) \end{align}

I do not understand how it is being done. Like how we got second line from the first line. Recurrence is really confusing for me. Hope you can explain it! Thank you!

asked Jan 27 '15 at 16:26

UserMoon

2

You know that $T(m)=T(m-1)+m$. Now set $m=n-1$. What do you get when you replace $m$ by $n-1$ in the expression $T(m)=T(m-1)+m$? – Git Gud Jan 27 '15 at 16:29
I get $T(n-1) = T(n-2) + (n-1)$ So then I just plug it in the formula at the first line for T(n-1), right? Thanks! – UserMoon Jan 27 '15 at 16:34
1

That's right.${}$ – Git Gud Jan 27 '15 at 16:35

Need help in understanding the procedure of expanding recurrence formula

0 Answers0