Sequences, Sums and Growth Rates

Arithmetic and geometric sequences, sigma notation and series, exponential growth and halving, and how growth rates lead to Big-O notation.

Sequences

A sequence in mathematics is an ordered list of numbers: a first term, a second term, and so on. Unlike a set, order matters and values may repeat. The terms are written with an index: a_1 is the first term, a_2 the second, and a_n the nth, a general term. Some books start counting at a_0; always check where the index starts.

IT is full of sequences: daily meter readings, monthly storage usage, the waits between retries, the sizes of a growing array. A sequence can be described in two ways:

  • With a direct formula for the nth term, such as a_n = 2^n. You can jump straight to term 30 without computing the others.
  • With a recurrence: the first term, plus a rule that builds each term from the previous ones, such as a_1 = 1, a_{n+1} = 2 \cdot a_n. The Fibonacci numbers (1, 1, 2, 3, 5, 8, …, each the sum of the two before it) are the best-known example; see tree-shaped recursion for how computing them naively goes wrong, and Fibonacci-like scales for their use in estimation.

Two kinds of sequences appear so often that they have their own names and formulas.

Arithmetic sequences: adding a fixed amount

Kestrel Energy's meter-data platform writes 2 GB of logs on the first day of a new month, and because customers keep joining, each day writes 0.5 GB more than the day before: 2, 2.5, 3, 3.5, … GB. An arithmetic sequence is a sequence in which each term is the previous term plus a fixed number, the common difference d. Here a_1 = 2 and d = 0.5.

To reach term n you start at a_1 and add d exactly n - 1 times (term 1 needs no additions, term 2 one, and so on):

a_n = a_1 + (n - 1) \cdot d

Day 30: a_{30} = 2 + 29 \cdot 0.5 = 2 + 14.5 = 16.5 GB. Plotted, an arithmetic sequence lies on a straight line; it is linear growth.

Adding up an arithmetic sequence

How much log data is written in the whole month? You could add 30 numbers, but there is a shortcut, traditionally credited to the young Carl Friedrich Gauss. Write the sum forward and backward and add the two lines term by term: 

forward:    2   + 2.5  + 3    + ... + 16   + 16.5
backward:   16.5 + 16  + 15.5 + ... + 2.5  + 2
pairs:      18.5 + 18.5 + 18.5 + ... + 18.5 + 18.5   (30 pairs)

Every pair adds up to the same number, first plus last (18.5). Thirty pairs make 30 \cdot 18.5 = 555, but that is the sum counted twice, so the month's total is 555 / 2 = 277.5 GB. In general, the sum of the first n terms is "the number of terms times the average of the first and last":

S_n = \frac{n \, (a_1 + a_n)}{2}

The most famous case is 1 + 2 + 3 + \cdots + n, with a_1 = 1 and a_n = n:

1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}

For n = 100 that is \frac{100 \cdot 101}{2} = 5050. You will meet this formula again below, when counting the steps of nested loops. 

first, step = 2.0, 0.5          # GB on day 1, extra GB per day
days = [first + (n - 1) * step for n in range(1, 31)]
print(days[:5], days[-1])
print(sum(days), 30 * (days[0] + days[-1]) / 2)
print(sum(range(1, 101)), 100 * 101 // 2)
[2.0, 2.5, 3.0, 3.5, 4.0] 16.5
277.5 277.5
5050 5050

Sigma notation and series

Writing "a_1 + a_2 + \cdots + a_n" gets clumsy. Mathematics uses the capital Greek letter sigma, \Sigma, for "sum":

\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n

Read it as "the sum of a_i for i from 1 to n". It has three parts:

  • the index (i), a counter that takes each whole number in turn;
  • the bounds: the start below the sigma (i = 1) and the end above it (n), both included;
  • the body to the right (a_i), the expression that is added for each value of the index.

For example \sum_{i=1}^{4} i^2 = 1 + 4 + 9 + 16 = 30. A sum written like this is a loop, and translates directly into Python. The only trap is that Python's range excludes its end, so "up to and including n" becomes range(1, n + 1): 

n = 4
total = 0
for i in range(1, n + 1):      # i = 1, 2, 3, 4
    total += i ** 2
print(total)
print(sum(i ** 2 for i in range(1, n + 1)))
print(sum(i ** 2 for i in range(n)))      # off by one: i = 0, 1, 2, 3
30
30
14

The sum of the terms of a sequence is called a series. A finite series stops after n terms; an infinite series keeps going, and may still add up to a finite number, as the next section shows. A capital pi, \prod, works the same way for products: \prod_{i=1}^{n} i = n!, the factorial.

Geometric sequences: multiplying by a fixed factor

A geometric sequence is a sequence in which each term is the previous term times a fixed number, the common ratio r. The powers of two, 1, 2, 4, 8, 16, …, form one with r = 2; halving, 64, 32, 16, 8, …, gives one with r = \frac{1}{2}. To reach term n you multiply by r exactly n - 1 times:

a_n = a_1 \cdot r^{\,n-1}

The geometric sum

Add the first 10 powers of two: S = 1 + 2 + 4 + \cdots + 512. Again there is a trick, this time with subtraction:

  1. Write the sum: S = 1 + 2 + 4 + \cdots + 256 + 512.
  2. Multiply every term by the ratio 2: 2S = 2 + 4 + 8 + \cdots + 512 + 1024.
  3. Subtract the first line from the second. All terms from 2 to 512 appear in both and cancel, leaving 2S - S = 1024 - 1.
  4. So S = 1023 = 2^{10} - 1.

That is the familiar fact that 10 bits, all set to 1, make 1023: the largest value of n bits is 2^n - 1. The same trick works for any ratio r \ne 1:

\sum_{k=0}^{n-1} a_1 r^k = a_1 + a_1 r + \cdots + a_1 r^{n-1} = a_1 \cdot \frac{r^n - 1}{r - 1}

When the ratio lies between −1 and 1, the terms shrink so fast that the infinite series has a finite total. Halving again and again, \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots, gets ever closer to 1 without passing it: each term covers half of the remaining gap. In general, for -1 \lt r \lt 1:

\sum_{k=0}^{\infty} a_1 r^k = \frac{a_1}{1 - r} 
print(sum(2 ** k for k in range(10)), 2 ** 10 - 1)
print(sum(0.5 ** k for k in range(1, 30)))     # 1/2 + 1/4 + ... (29 terms)
print(sum(0.5 ** k for k in range(1, 60)) == 1.0)
1023 1023
0.9999999981373549
True

The partial sum with 29 terms falls short of 1 by 2^{-29}. With 59 terms the difference is smaller than a floating-point number near 1 can show, so the result prints as exactly 1.0 (see Floating-Point Numbers).

The geometric sum explains why a dynamic array can grow by doubling and still be fast on average. Each time it is full it copies everything into a space twice as big. To reach n items it has copied at most 1 + 2 + 4 + \cdots + \frac{n}{2} \lt n items in total, less than one copy per item. The programming page calls this amortized cost. (A Python list works the same way with a smaller factor: CPython grows it by about 12.5% each time. Any fixed factor keeps the average cost per item constant.)

Exponential growth, doubling and halving

Kestrel's archive of meter data is 40 TB and grows by 25% per year. Growing by 25% means multiplying by 1.25 each year, so the archive sizes form a geometric sequence. Quantities that are multiplied by the same factor in every period show exponential growth:

V_t = V_0 \cdot (1 + g)^t

where V_0 is the starting value, g the growth rate per period as a fraction (0.25), and t the number of periods. The variable t is in the exponent, hence the name. When will the archive pass the 100 TB that the current storage cluster holds?

  1. Solve 40 \cdot 1.25^t = 100, so 1.25^t = 2.5.
  2. Take logarithms of both sides: t \cdot \ln 1.25 = \ln 2.5, so t = \frac{\ln 2.5}{\ln 1.25} \approx 4.1 years (see Powers, Roots and Logarithms).
  3. So the cluster is full a little over four years from now; at the end of year 5 the archive is about 122 TB.

Doubling time and the rule of 70

Exponential growth has a fixed doubling time: however big the quantity is, it takes the same number of periods to double. Solving (1 + g)^t = 2 gives t = \frac{\ln 2}{\ln(1 + g)}. For small growth rates there is a mental shortcut, the rule of 70: divide 70 by the growth percentage. At 7% per year, 70 / 7 = 10 years; the exact answer is 10.24. (It works because \ln 2 \approx 0.693 and \ln(1 + g) \approx g for small g.) 

import math

size, year = 40.0, 0          # TB
while size <= 100:
    size *= 1.25
    year += 1
print(year, round(size, 1))
print(round(math.log(2.5) / math.log(1.25), 2))

# Doubling time of something that grows 7% per period: rule of 70 vs exact
print(round(70 / 7, 1), round(math.log(2) / math.log(1.07), 2))
5 122.1
4.11
10.0 10.24

Halving

Turn it around: a quantity that is halved each step shrinks exponentially. How many halvings does it take to get from n down to 1? That is the number k with 2^k = n, which is \log_2 n. Starting at 1,000,000 you need 20 halvings, because 2^{20} = 1{,}048{,}576. That is why binary search, which halves the part of a sorted list that is still in play at every step, finds any item among a million in about 20 comparisons. 

import math

remaining, steps = 1_000_000, 0
while remaining > 1:
    remaining = math.ceil(remaining / 2)     # keep the larger half
    steps += 1
print(steps, math.ceil(math.log2(1_000_000)))
20 20

Exponential backoff

When a request to a busy service fails, retrying immediately and repeatedly makes the overload worse. Exponential backoff is a retry strategy in which the wait before each new attempt grows geometrically, usually doubling, up to a maximum (the cap). With a base wait of 1 second and a cap of 60 seconds, the wait before retry k (counting from 0) is

w_k = \min(2^k, 60) \text{ seconds}
A bar chart of the wait before each of eight retries: 1, 2, 4, 8, 16 and 32 seconds, doubling each time, and then 60 and 60 seconds, held down by a horizontal cap line at 60 seconds. 0 15 30 45 60 1 0 2 1 4 2 8 3 16 4 32 5 60 6 60 7 retry k (counting from 0) wait (s) cap: 60 s
Retry 0 waits 2^0 = 1 second; the waits of 1, 2, 4, … seconds double until the cap of 60 seconds takes over at retry 6.

How long has a client waited in total after the first k retries, before the cap is reached? That is a geometric sum: 1 + 2 + 4 + \cdots + 2^{k-1} = 2^k - 1 seconds. After the six uncapped waits, 63 seconds have passed; the two capped waits add 120 more. 

# Exponential backoff: wait 1, 2, 4, ... seconds, capped at 60
waits = [min(2 ** attempt, 60) for attempt in range(8)]
print(waits, sum(waits))
print(sum(waits[:6]), 2 ** 6 - 1)
[1, 2, 4, 8, 16, 32, 60, 60] 183
63 63

In practice a random amount, called jitter, is added to each wait so that many clients that failed at the same moment do not all retry at the same moment too. The web page shows how webhook senders and API clients use this: delivery and retries.

Comparing growth rates

How does the work an algorithm does grow when its input grows? The answer is almost always one of a few families of functions, and the differences between them dominate everything else once the input is large. Here they are for an input of a million items: 

import math

n = 1_000_000
print(f"{'O(1)':<12}{1:>16,}")
print(f"{'O(log n)':<12}{math.ceil(math.log2(n)):>16,}")
print(f"{'O(n)':<12}{n:>16,}")
print(f"{'O(n log n)':<12}{round(n * math.log2(n)):>16,}")
print(f"{'O(n^2)':<12}{n * n:>16,}")
O(1)                       1
O(log n)                  20
O(n)               1,000,000
O(n log n)        19,931,569
O(n^2)      1,000,000,000,000

An exponential algorithm, 2^n, is not even in the table: for n = 1{,}000{,}000 the number has over 300,000 digits. A useful way to feel the differences is to ask what happens when the input doubles:

Growth Example When n doubles, the work …
logarithmic, \log_2 n binary search grows by one step
linear, n reading every log line once doubles
n \log_2 n good sorting algorithms slightly more than doubles
quadratic, n^2 comparing every pair quadruples
exponential, 2^n trying every subset is squared (2^{2n} = (2^n)^2)

From sums to Big O

The sum formulas on this page are how such growth classes are found. A script that compares every pair of the n meters in a list (to find duplicate serial numbers, say) uses two nested loops: the first meter is compared with n - 1 others, the second with n - 2 new ones, and so on. The total number of comparisons is an arithmetic sum:

(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} 
def comparisons(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):    # every pair once
            count += 1
    return count

for n in (10, 100, 1000):
    print(n, comparisons(n), n * (n - 1) // 2)
10 45 45
100 4950 4950
1000 499500 499500

For large n the n^2 term dominates and the factor \frac{1}{2} does not change how the work grows: ten times more meters means about a hundred times more comparisons. Big O notation keeps exactly that dominant term and drops the constants, so this script is O(n^2). It is also why the base of a logarithm is not written inside Big O: \log_2 n and \log_{10} n differ only by a constant factor (\log_2 n \approx 3.32 \cdot \log_{10} n), so O(\log n) means either. The full treatment, with the formal definition and the common classes, is on Algorithmic Complexity; see also counting steps.