Adding Numbers from 1 to N
This is one of those little problems with a background story that can make us truly appreciate the ingenuity of mathematicians. There seem to be multiple versions of this story, but the most popular one can be summarised as follows:
Gauss (renowned mathematician and child prodigy) was 10 years of age and was part of an arithmetic class. His teacher came up with the idea of making his pupils add all the integers from 1 to 100, presumably to keep them busy and free himself to do other things. Gauss quickly came up with the answer: 5050. The teacher allegedly thought the child had cheated, but in reality he had applied the technique we will discuss on this post.
Whilst the invention of this method precedes the works of Carl Friedrich Gauss, he reinvented and popularised it with this anecdote from his childhood. Be that as it may, how was he able to produce the answer to the problem faster than the other pupils?
Solution
The solution to the problem is more generally called an arithmetic series which can be defined as the sum of the members of a finite arithmetic progression. An arithmetic progression is a sequence of numbers in which the difference between two consecutive numbers is constant. Take for example:
0 3 6 9 12 15
The previous is an arithmetic progression with a common difference of 3.
The question remains, how did Gauss reach the solution so quickly? To understand how he did it, it is useful to visualise the sequence of numbers from 1 to 100 on a line, and below the same sequence but in reversed order, like so:
1 + 2 + 3 + 4 + 5 + ... + 98 + 99 + 100
100 + 99 + 98 + 97 + 96 + ... + 3 + 2 + 1
We will notice an interesting pattern here: adding each vertical pair of numbers gives the same result of 101.
1 + 2 + 3 + 4 + 5 + ... + 98 + 99 + 100
100 + 99 + 98 + 97 + 96 + ... + 3 + 2 + 1
----------------------------------------------------
101 + 101 + 101 + 101 + 101 + ... + 101 + 101 + 101
With this knowledge and also knowing that there are 100 pairs, we can compute a total sum:
101 * 100 = 10100
However, we have included duplicate pairs (e.g. 100 + 1 = 1 + 100) and we only care about unique addition of pairs. We can solve this by dividing the previous total by 2, thus removing equivalent pairs:
10100 / 2 = 5050
And now we have reached the solution to the problem of adding all the integers from 1 to 100 without having to add up the elements from 1 to 100 iteratively. There are many ways to acquire intuition behind arithmetic series, but this one I found the easiest to grasp.
Formula and proof
From the reasoning above we can derive a formula that can be used to compute the sum of all integers from $1$ to any number $n$. The formula is the following:
$$S = \dfrac{n(n + 1)}{2}$$
To derive it we can repeat the process in the previous section but applied to an arbitrary number $n$. We first write the arithmetic series $S$ from 1 to $n$ at the top, and from $n$ to 1 at the bottom:
S = 1 + 2 + 3 + 4 + 5 + ... + (n-2) + (n-1) + n
S = n + (n-1) + (n-2) + (n-3) + (n-4) + ... + 3 + 2 + 1
If we add the two equations we get:
S = 1 + 2 + 3 + 4 + 5 + ... + (n-2) + (n-1) + n
S = n + (n-1) + (n-2) + (n-3) + (n-4) + ... + 3 + 2 + 1
-------------------------------------------------------------------------
2S = (n+1) + (n+1) + (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)
Again we notice the pattern of all the pairs adding up to the same result, in this case $(n+1)$. We can simplify the expression above by factorising it, since $(n+1)$ is added $n$ times.
$$2S = n(n+1)$$
Finally, we want to represent the equation with respect to $S$, so we isolate it:
$$S = \dfrac{n(n+1)}{2}$$
QED
Application to algorithmic complexity analysis
As it is often the case, I write about mathematical definitions after I see them manifest in more applied areas of knowledge. Finding them in these places makes me develop an appreciation of their universality and usefulness. In the case of the arithmetic series in particular, I was revisiting sorting algorithms and realised that the method to calculate the time complexity for algorithms like selection, insertion and bubble sort starts with the formula above.
Imagine we have an array of $n$ elements, the number of iterations for these algorithms can be estimated by $n + (n-1) + (n-2) + (n-3) + …\ + 3 + 2 + 1$. This is because for each iteration, the size of the array that needs to be traversed decreases by 1. This value can be represented using the formula we derived.
However for complexity analysis we are concerned about how an algorithm scales, not about the exact number of iterations it will require to perform the task. For this we need to represent the formula in a slightly different way:
$$\dfrac{n(n+1)}{2} = \dfrac{n^2 + n}{2} = \dfrac{n^2}{2} + \dfrac{n}{2}$$
The way to represent time complexity is by using Big O notation, for which we only care about terms with the highest growth as $n$ becomes larger. We remove $\dfrac{n}{2}$ and only $\dfrac{n^2}{2}$ remains. Moreover, it is also common to ignore any factors that do not depend on $n$, so we remove the $\dfrac{1}{2}$. The result for the time complexity is expressed as $O(n^2)$ which can be read as “oh $n$ squared” or “quadratic” time complexity.
Algorithms with $O(n^2)$ complexity are usually considered to be “slow”, but can nevertheless be useful depending on the context in which they are applied.
External Resources
Below I list the resources I found useful to write this post and also further reading and watching: