1
$\begingroup$

this is a example from my book

Write several elements of the recursion, and see if you can find a pattern.

T(n) = T(n – 1) + n

T(n –1) = T(n – 2) + (n –1)

T(n –2) = T(n – 3) + (n –2)

T(n –3) = T(n – 4) + (n –3)

Now substitute:

T(n) = T(n – 1) + n

= [T(n – 2) + (n –1)] + n

= [[T(n – 3) + (n –2)] +(n –1)] + n

= [[[T(n – 4) + (n –3)] + (n –2)] +(n –1)] + n

= T(n – k) + Σki=1(n –i+1) = T(n – k) + nk – ((k – 1)k)/2

I dont understand how they got

T(n – k) + nk – ((k – 1)k)/2

How did they go from this line

= [[[T(n – 4) + (n –3)] + (n –2)] +(n –1)] + n

to

= T(n – k) + Σki=1(n –i+1) = T(n – k) + nk – ((k – 1)k)/2

?

$\endgroup$

1 Answer 1

1
$\begingroup$

The line just above "I don't understand how they got" is incorrect (or at least confusing). You have the pattern $$\begin{align} T(n)&=T(n-1)+n\\ &=T(n-2)+(n-1)+n\\ &=T(n-3)+(n-2)+(n-1)+n\\ &=T(n-4)+(n-3)+(n-2)+(n-1)+n \end{align}$$ and it appears that $$ T(n)=T(n-k)+[(\color{red}{n-k}+1)+(\color{red}{n-k}+2)+\cdots+(n-1)+n] $$ We can write the part in brackets as $$ \sum_{i=1}^k(n-k+i) $$ and recognize that this is $$ \sum_{i=1}^k(n-k)+\sum_{i=1}^ki=(k(n-k))+\frac{k(k+1)}{2} $$ Note that the first sum on the left is just the sum of $k$ copies of $n-k$ and the other sum on the left is just the sum $1+2+\dots+k$. A bit of simplification on the right gives you $$ T(n)=T(n-k)+nk-\frac{k(k-1)}{2} $$ as required.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .