Last updated June 8, 2025
Sum of arithmetic sequences
In math, a summation is used to find the sum of all numbers in a sequence. For example, the sum of all whole numbers from 1 to 100 can be represented as:
\[\sum_{n = 1}^{100} n = 1 + 2 + 3 + \dots + 99 + 100 = 5050\]
To calculate this sum by hand would be tedious, and you might think "we have computers for this". Plenty of online calculators have a built-in way to find summations, how were they programmed to do that? You might notice summation notation is very similar to the idea of a for loop in programming; a program to calculate the above sum might look something like this:
sum = 0
for (n = 1; n <= 100; n++) {
sum = sum + n
}
print(sum)
What if you needed to find the sum of all whole numbers from 1 up to a much, much larger number than 100, though? Using a for loop would still be way faster than calculating it by hand, but you'd start putting a strain on the computer. A summation like this has a time complexity of \(O(n)\): if ten times more numbers are being summed, it'll take ten times longer to calculate.
If the numbers you need to add up are a finite arithmetic sequence, there's a faster way to find their sum than actually adding each number. Notice that if you add the first number in the sequence to the last, the second to the second-to-last, the third to the third-to-last, and so on, each of these sums is the same: \(1 + 100 = 2 + 99 = 3 + 98 = \dots = 101\). Since there are 100 numbers in the sequence, 100 times 101 equals 10100— exactly twice the sum of all the numbers. We can now calculate the sum with a time complexity of \(O(1)\): the calculation can be performed in the same number of steps regardless of how many numbers are being summed.
\[\sum_{n = 1}^{100} n = \frac{100 (1 + 100)}{2} = 5050\]
Fibonacci numbers
If you need to add up numbers that don't follow any particular pattern, there's no way to do it faster than \(O(n)\). You can often find faster ways to work with sequences that follow complex patterns, though, like the Fibonacci sequence.
In \(O(n)\) time
To find the \(n^{\text{th}}\) number in the sequence, you would normally add the previous two numbers. The zeroth number in the series is \(F_0 = 0\) and the first number is \(F_1 = 1\), so \(F_2 = F_0 + F_1 = 1\), \(F_3 = F_1 + F_2 = 2\), and so on. A program to calculate the 50th Fibonacci number in this way might look like this:
numbers = []
numbers[0] = 0
numbers[1] = 1
for (n = 2; n <= 50; n++) {
numbers[n] = numbers[n - 1] + numbers[n - 2]
}
print(numbers[50])
In math:
\[\begin{split} F_{50} &= \sum_{n = 2}^{50} F_{n-2} + F_{n-1} \\ &= (F_0 + F_1) + (F_1 + F_2) + \dots + (F_{48} + F_{49}) \\ &= (0 + 1) + (1 + 1) + \dots + (4,807,526,976 + 7,778,742,049) \\ &= 12,586,269,025 \end{split}\]
This method has the same time complexity as using a for loop to calculate a sum, \(O(n)\). If you were to calculate the first 50 Fibonacci numbers in this way and then use a loop to find their sum, what would the time complexity be?
numbers = []
numbers[0] = 0
numbers[1] = 1
for (n = 2; n <= 50; n++) {
numbers[n] = numbers[n - 1] + numbers[n - 2]
}
sum = 0
for (n = 0; n <= 50; n++) {
sum = sum + numbers[n]
}
print(sum)
Since we're using two loops, you might think it's \(O(n) + O(n) = 2O(n)\), but constants are actually disregarded in time complexity, so it's still just \(O(n)\). Which isn't to say that using a single loop doesn't make a difference, especially if all you care about is the sum and you're working with large numbers:
prev2 = 0
prev1 = 1
sum = 1
for (n = 2; n <= 50000; n++) {
Fn = prev2 + prev1
sum = sum + Fn
prev2 = prev1
prev1 = Fn
}
print(sum)
In \(O(1)\) time
There are faster ways to calculate both the \(n^{\text{th}}\) Fibonacci number and the sum of the first \(n\) numbers. We can represent the Fibonacci sequence \(F(n)\) with a generating function:
\[F(n) = 0n^0 + 1n^1 + 1n^2 + 2n^3 + 3n^4 + 5n^5 + 8n^6 + 13n^7 + \dots\]
walk through deriving closed form for F_n and sum from F_0 to F_n
Other examples to explore:
Binomial coefficients
Flood fill