Summations and sequences

An arithmetic progression has a constant difference d: a, a + d, a + 2d, …. Its sum is the number of terms times the average of the first and last: S = n(a + l) / 2. For 1 + 2 + … + n this is n(n + 1) / 2, which is why a nested loop where the inner bound grows by one is O(n²).

Gauss paired the first and last terms, which each sum to n + 1. Step through the pairing.

1static long sumTo(int n) {                       // 1 + 2 + ... + n
2    long total = 0;
3    for (int i = 1; i <= n; i++) total += i;     // n additions
4    return total;
5}
6
7static long sumToFormula(int n) {
8    return (long) n * (n + 1) / 2;               // n/2 pairs, each summing to n + 1
9}

A geometric progression multiplies by a ratio r: a, ar, ar², …. The sum of n terms is a(rⁿ - 1) / (r - 1) for r ≠ 1. With r = 2: 1 + 2 + 4 + … + 2ᵏ⁻¹ = 2ᵏ - 1, so the total work in the last level of a binary tree is about the same as all the levels above it combined.

For |r| < 1 the infinite sum converges to a / (1 - r); for example n + n/2 + n/4 + … < 2n, which explains why halving costs total O(n).

Three formulas cover most loop analysis: Σi = n(n + 1)/2, Σi² = n(n + 1)(2n + 1)/6 and Σi³ = (n(n + 1)/2)². They show that a triple loop whose bounds grow is Θ(n³), and that Σi² grows like n³/3.

Check any formula with small n before relying on it: Σi² for n = 4 is 1 + 4 + 9 + 16 = 30 and 4·5·9/6 = 30. Use long when n is large because n(n + 1) overflows int above about 46,340.

1long n = 100_000;
2long sum  = n * (n + 1) / 2;                 // 5000050000
3long sumSq = n * (n + 1) * (2 * n + 1) / 6;  // 333338333350000

1static long sumTo(int n) {                       // 1 + 2 + ... + n
2    long total = 0;
3    for (int i = 1; i <= n; i++) total += i;     // n additions
4    return total;
5}
6
7static long sumToFormula(int n) {
8    return (long) n * (n + 1) / 2;               // n/2 pairs, each summing to n + 1
9}

A prefix-sum array stores p[i] = sum of the first i elements. Any range sum then costs O(1): sum(l..r) = p[r + 1] - p[l]. Building takes O(n), so q queries cost O(n + q) rather than O(nq).

Change the array and query range in the animation to see the subtraction.

1int[] a = {3, 1, 4, 1, 5};
2long[] p = new long[a.length + 1];
3for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];   // [0, 3, 4, 8, 9, 14]
4long range = p[4] - p[1];     // sum of a[1..3] = 1 + 4 + 1 = 6

1static int[] buildPrefix(int[] arr) {
2    int[] prefix = new int[arr.length + 1];      // prefix[i] = arr[0] + ... + arr[i-1]
3    for (int i = 0; i < arr.length; i++) {
4        prefix[i + 1] = prefix[i] + arr[i];
5    }
6    return prefix;
7}
8
9static int rangeSum(int[] prefix, int l, int r) {   // sum of arr[l..r]
10    return prefix[r + 1] - prefix[l];
11}

The harmonic series Hₙ = 1 + 1/2 + 1/3 + … + 1/n grows like ln n + 0.5772 (so about 14.4 at n = 10⁶). It shows up in loops such as for i in 1..n: for j = i; j <= n; j += i, which run n/1 + n/2 + … + n/n = n·Hₙ = O(n log n) steps. The sieve of Eratosthenes has the same structure.

Because Hₙ grows so slowly, n·Hₙ is only a little more than n.

1int n = 1_000_000; long steps = 0;
2for (int i = 1; i <= n; i++) for (int j = i; j <= n; j += i) steps++;
3// steps = 13970034 = about n * (ln n + 0.577) = 1e6 * 14.39

A telescoping sum has terms that cancel in pairs, leaving only the ends. Since 1/(i(i + 1)) = 1/i - 1/(i + 1), the sum over i = 1..n equals 1 - 1/(n + 1). Differences in a prefix-sum array telescope in the same way: Σ(p[i + 1] - p[i]) = p[n] - p[0].

Look for a term that can be written as f(i) - f(i + 1).

1// sum_{i=1..n} 1/(i(i+1)) = 1 - 1/(n+1)
2int n = 9;
3double s = 0;
4for (int i = 1; i <= n; i++) s += 1.0 / (i * (i + 1));
5// s = 0.9 = 1 - 1/10

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2): 0, 1, 1, 2, 3, 5, 8, 13, …. Naive recursion repeats work exponentially; memoisation or a simple loop computes F(n) in O(n) time and O(1) space. F(92) = 7,540,113,804,746,346,429 is the largest value that fits in long.

Compare the call counts with and without memoisation in the animation.

1static long fib(int n) {          // valid for n <= 92
2    long a = 0, b = 1;
3    for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
4    return a;
5}

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}