math Common summations in computer science Gauss's sum: 1 + 2 + 3 + ... + n


Example

The sum

1 + 2 + 3 + ... + n

Simplifies to

n(n+1) / 2.

Notice that this quantity is Θ(n2).

This shortcut arises frequently in the analysis of algorithms like insertion sort or selection sort.

Numbers of the form n(n+1)/2 are called the triangular numbers.