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?
Best Answer
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}$$