Bubble sort complexity calculation, unsure how it went from one step to another.

Question

I'm looking at my textbooks steps for calculating the complexity of bubble sort...and it jumps a step where I don't know what exactly they did.

I see everything up to that point using summation rules and all, but am unsure about that jump. Any help on explaining more how they got that?

Answer 1

$$\sum_{i = 0}^{n-2} (n - 1 -i) = (n -1) + (n-2) + ... + 2 + 1 = \frac{(n -1)n}{2}$$

It is the sum of the simplest arithmetic series.

Answer 2

Plug in the possible values of $i$ into the summation! You get: $$ (n-1) + (n-2) + \cdots + 2 + 1 $$ which is the sum of consecutive integers from 1 to $(n-1)$. This sum has a well-known formula: $$ {(\mbox {last term})\cdot(\mbox{last term} + 1)\over 2}={(n-1)n\over 2} $$