The Story of Gauss and 1 + 2 + 3 + … + 100

When learning about algorithms, one of the most important ideas in computer science is the Big O Notation. It helps us measure how efficient an algorithm is — especially as the size of the problem gets bigger.

To introduce this concept, let’s travel back to the classroom of a young mathematical genius: Carl Friedrich Gauss (1777 – 1855).
Legend has it that when Gauss was a child, his teacher asked the class to add all the integers from 1 to 100:

1 + 2 + 3 + 4 + ⋯ + 100

The teacher likely expected the students to take a long time adding each number one by one.

But Gauss noticed a clever pattern.

Gauss’ Clever Pairing Method

Carl Friedrich Gauss wrote down the sum adding all the numbers from 1 to 100 in ascending order (from 1 to 100):

1 + 2 + 3 + 4 + ... + 97 + 98 + 99 + 100

Underneath he wrote the same sum, using the same 100 numbers but this time, writing them in descending order (from 100 to 1):

100 + 99 + 98 + 97 + ... + 4 + 3 + 2 + 1

He then paired all these numbers up and realised that each pair added up to 101:

So the total is of all these pairs is :

Sum of all pairs =  100 × 101 = 10,100

But we now have twice as many numbers as needed to caluclate the sum of all the numbers from 1 to 100. So we need to divide this result by 2:

Sum of all numbers from 1 to 100 = 10,100 / 2 = 5,050 

And just like that, Gauss found the answer instantly. From Gauss’ reasoning, we can generalise his approach using the following formula:

We can apply this formula with n=100 or any other value (e.g. n=1,000 or n=1,000,000)

Using an Algorithms

Now let’s compare two approaches to calculate our sum:

1. Iterative addition (adding numbers one by one)
2. Gauss’ formula method

Method 1: Iterative Approach

Algorithm (Pseudocode)

total = 0
FOR i FROM 1 TO 100
    total = total + i
END FOR
PRINT total

Python Implementation

def iterative_sum(n):
    total = 0
    for i in range(1, n+1):
        total += i
    return total

print(iterative_sum(100))

This method performs 100 additions when n = 100.

Method 2: Gauss’ Formula

Algorithm (Pseudocode)

total = n × (n + 1) / 2
PRINT total

Python Implementation

def gauss_sum(n):
    return n * (n + 1) / 2

print(gauss_sum(100))

No matter how large n is, this algorithm performs:

• 1 multiplication
• 1 addition
• 1 division

Python Code

We have implemented both functions in the Python IDE below. Using the time library we are also measuring how long the computer took to calculate the sum.
Based on our analysis, we believe that the Gauss formula should be more efficient especially with a very large number for n (e.g. n=1,000,000)

Comparing Efficiency Using Big O Notation

The Big O Notation is used to describe how the running time of an algorithm grows as the input size (n) increases.

With an iterative approach, the loop used to calculate our sum runs n times.
If:

• n = 100 → 100 operations
• n = 1,000 → 1,000 operations
• n = 1,000,000 → 1,000,000 operations

The completion time of this algorithm is pro-rata to the value of n. This is called O(n) — linear time complexity.

---

Using the Gauss formula, the formula only needs to be executed once, regardless of n. The algorithm always performs the same number of operations — regardless of n.

• n = 100 → same steps (~3 operations)
• n = 1,000 → same steps (~3 operations)
• n = 1,000,000 → same steps (~3 operations)

This is called O(1) — constant time complexity.

What Happens as n Gets Bigger?

n	Iterative Operations	Gauss Operations
100	100	~3
1,000	1,000	~3
1,000,000	1,000,000	~3
1,000,000,000	1,000,000,000	~3

As n grows, the difference becomes enormous.
This is why algorithm efficiency matters.

When evaluating the efficiency of an algorithm, the Big O notation helps us answer the following questions:

• Will this program scale?
• What happens when the dataset gets huge?
• Is there a smarter way to solve this problem?

Gauss did not just calculate a sum. He found a more efficient algorithm.
And that is exactly what computer scientists do every day: they use algorithmic thinking to try to find efficient way of solving a problem.