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.
