Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to understand different sorting algorithms and their BigO notation. Suppose, I'm using insertion sort and I have the worst case:

6 | 5 | 4 | 3 | 2 | 1

The number of comparisons will be $1 + 2 + 3 + 4 + 5 = 15$ or we can write it like:

1 + 2 + 3 + ... + (n-1)

Also we can use formula to calculate number of comparisons for this sequence:

n(n-1)/2

But it's not clear for me how to convert:

1 + 2 + 3 + ... + (n-1) --> n(n-1)/2

Can you help?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Write the sequence twice, once the "right" way, and once in reverse, then add vertically: $$\begin{array}{cccccc} 1 & + & 2 & + & 3 & + & \ldots & + & (n-1) \\ (n-1) & + & (n-2) & + & (n-3) & + & \ldots & + & 1 \\ \hline n & + & n & + & n & + & \ldots & + & n \end{array}$$ Now, what does the new sum add up to? Well, there's $n-1$ "$n$"'s to add up. Thus we have $n(n-1)$ as the new sum.

BUT, we know the new sum is twice the old one (after all, we added it twice). So, divide the new sum by two to get the old sum: $$\frac{n(n-1)}{2}$$

share|improve this answer
    
Is it a general approach of solving such tasks? –  viakondratiuk Jan 31 '13 at 13:00
    
@viakondratiuk Unfortunately, this isn't really a "general" way, but more of a way to get an intuition. For more complex summations (e.g. sums of sums, or sums of squares), I use the formulas found here: en.wikipedia.org/wiki/… –  anorton Jan 31 '13 at 13:04
    
Thank you for your help. –  viakondratiuk Jan 31 '13 at 13:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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