0
$\begingroup$

I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs.

I know how one can get formula for arithmetic series when we deal with while loop header, I mean 2+3+...+n equals to (n*(n+1) / 2) - 1. But what I do not understand is how one can get formula for while loop body:

summation notation on page 27

It is obvious, that we execute while loop body one time less, than while loop header, because of the final conditional test. Hence, we should subtract one. But how do we get n * (n - 1) / 2?

$\endgroup$
2
$\begingroup$

$$\sum_{j=2}^n \left(j - 1\right) = \sum_{i=1}^{n-1} i$$

$\endgroup$
2
  • 1
    $\begingroup$ Alternatively $\sum_{j=2}^n (j-1) = \sum_{j=2}^n j - \sum_{j=2}^n 1 = n(n+1)/2 - 1 - (n-1) = n(n-1) / 2$. $\endgroup$ – Stef Jun 18 at 10:23
  • $\begingroup$ Thank you, Stef and Pseudonym. Yes, both statements make sense to me, since we are subtracting one n times from index two. $\endgroup$ – Vlad Mikheenko Jun 18 at 10:37

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.