Sum of Naturals

The sum 1 + 2 + … + n can be computed with a loop in O(n), or with Gauss's formula in O(1):

S = n × (n + 1) / 2

Why it works: write the sum forwards and backwards, then add the two rows column by column. Every column sums to n + 1, and there are n columns, so twice the sum is n(n+1).

A closed-form formula is always worth looking for when a loop just adds up a regular pattern.