Imperial College London – Department of Computing
MSc in Computing Science
580: Algorithms
Background: Series
Timothy Kimber
To determine the time taken by an algorithm we are often faced with evaluating the sum of a
sequence of related terms such as this:
T (N) = c + 2c + · · · + (N − 1)c + Nc (1)
where each term might be the time taken in one iteration of a loop. Such a sum is called a
series. If each iteration takes the same amount of time the answer is simple, but in the example
above, the time increases incrementally, by an amount c. This complicates the calculation. To
calculate a bound we can probably do away with the constant c and just count the number of
times some representative instruction is executed. In this case the series is simplified to:
1 + 2 + · · · + (N − 1) + N (2)
but it is essentially the same problem.
A second common form of series is:
Nc + (N/2)c + (N/4)c + · · · + 2c + c (3)
in which each term is a multiple (here half) of the previous one. This might represent the time
taken at each level of recursion in a divide and conquer algorithm.
Arithmetic Series
The first form, such as (1) or (2), is called an arithmetic series. In an arithmetic series there is
always a common difference between succesive terms. The general form of an arithmetic series
with k terms is
a + (a + d) + (a + 2d) + · · · + (a + (k − 1)d) (4)
where a is the first term and d is the common difference. This is also written, more succinctly,
as:
1
k−1∑
i=0
a + id (5)
In (1) both a and d equal c, and in (2) both a and d are 1. However, a does not have to equal
d: each can be any real number.
Solving Arithmetic Series
Any arithmetic series can be solved using the following method. Ultimately, this method pro-
vides us with a simple formula to solve the series, but understanding where this formula comes
from certainly helps me remember what it is.
We start by creating a second series. The new series is simply the reverse of the first. Taking
(2) as an example, these two series are:
1 + 2 + . . . + (N − 1) + N
N + (N − 1) + . . . + 2 + 1
Adding these together, term-by-term, gives another series
(N + 1) + (N + 1) + · · · + (N + 1) + (N + 1) (6)
As you can see, every term in (6) is the sum of the first and last terms of (2). Series (6) obviously
equates to N(N + 1), since it contains N terms that are all N + 1. So, if the solution (sum) of
the original series (2) is s, then N(N + 1) = 2s, and so
s =
N(N + 1)
2
. (7)
Since the difference between successive terms is always a constant d, the same method can be
applied to any arithmetic series. So, given
Sk = a1 + · · · + ak , (8)
we have
Sk =
k(a1 + ak)
2
. (9)
2
Geometric Series
The second form, such as (3), is called an geometric series. In a geometric series there is always
a common ratio between succesive terms. The general form of a geometric series with k terms
is:
a + ar + ar2 + · · · + ar(k−1) (10)
where a is the first term and r is the common ratio. This is also written:
k−1∑
i=0
ari . (11)
Solving Geometric Series
The method to solve geometric series is similar, and alomst as simple, as the one for arithmetic
series. Rather than collapsing all the terms to be the same value, this method eliminates all
but two terms from the calculation.
A second series is again created. This time we multiply the original series by r to get the new
one. Taking (3) as an example, r = 1/2 and these two series are:
Nc + (N/2)c + · · ·+ 2c + c
(N/2)c + · · ·+ 2c + c + c/2
All but two of the terms in these are identical, and taking the difference we are left with Nc−c/2.
If the solution (sum) of (3) is s, then we have Nc− c/2 = s− s/2, so
s/2 = Nc− c/2 ,
and
s = 2Nc− c .
Naturally, this works for any geometric series. Given
Sk = a + ar + ar
2 + · · · + ar(k−1)
we have
Sk − rSk = a− ark , (12)
and so
Sk =
a(1 − rk)
(1 − r)
. (13)
3
If we remember how we got to (13) we can easily adapt it for different situations. Firstly,
applying (13) suggests we know how many terms there are. If we simply know the first and last
terms of the series (and the common ratio), we can rewrite a and ark in (12) as a1 and rak,
giving
Sk =
a1 − rak
(1 − r)
. (14)
The forms of the solution above are most suitable when r < 1, because the result of Sk − rSk and 1 − r will be positive. If r > 1 then it makes sense to reorganise (12) to be
rSk − Sk = ark − a , (15)
and so
Sk =
a(rk − 1)
(r − 1)
, (16)
or equivalently
Sk =
rak − a1
(r − 1)
. (17)
4