Math for Algorithms

A knockout tournament starts with 64 teams. In every game, two teams play and the loser goes home. You need to know how many rounds it takes to find a champion, and how many games that is in total. You also want to compare it with a league, where each of the 64 teams plays every other team once.

The answers are 6 rounds, 63 games and 2,016 games. With the right idea, each takes a few seconds to work out. Those same few ideas are what you use to estimate the cost of an algorithm.

#Halving: logarithms

Each round of the tournament halves the number of teams: 64, 32, 16, 8, 4, 2, 1. That is 6 halvings. The number of times you can halve n before you reach 1 has a name: the logarithm base 2 of n, written log₂ n. So log₂ 64 = 6.

The same fact read backwards: 2 multiplied by itself 6 times is 64, written 2⁶ = 64. A logarithm just asks "which power of 2 gives me n?"

When n is not a power of 2, a program that halves with whole numbers rounds down each time. Step through it for 100.

steps = 0while n > 1:  n = floor(n / 2)  steps = steps + 1return steps

Logarithms grow very slowly. That is why any algorithm that throws away half of the remaining work at each step, like binary search, is so fast.

Remember one anchor: 2¹⁰ = 1,024, which is about a thousand. Every factor of 1,000 adds about 10 to the logarithm.

#Doubling: powers of two

Doubling is halving run backwards, and it explodes just as fast as halving shrinks. If you can include or leave out each of n items, there are 2 choices for the first, 2 for the second, and so on: 2ⁿ ways in total. With 3 toppings there are 2³ = 8 possible pizzas, counting the plain one. With 30 toppings there are over a billion.

That is why an algorithm that tries every subset is only usable for small inputs, around 20 to 25 items. It is also why the naive Fibonacci in Recursion was so slow: each call made up to two more, so the number of calls multiplied by a constant (about 1.6) every time n went up by 1. Anything that multiplies at each step grows like a power, and powers explode.

Now count the tournament games round by round: 32 + 16 + 8 + 4 + 2 + 1 = 63. A sum of halving amounts like this always comes out just under twice the biggest term. In general 1 + 2 + 4 + ... + 2ᵏ = 2ᵏ⁺¹ − 1.

There is also a faster way to see 63: every game sends exactly one team home, and 63 teams must go home for one to be left. Counting what each step removes is often easier than adding up the steps.

#Adding up 1 + 2 + ... + n

This sum shows up whenever an inner loop gets one step longer (or shorter) each time around. The shortcut: write the sum twice, once forward and once backward, and pair them up.

Each row of the rectangle holds one forward number and one backward number, and every row adds up to n + 1. There are n rows. So:

1 + 2 + ... + n = n(n + 1) / 2. For n = 100 that is 100 × 101 / 2 = 5,050.

The important part for algorithms is the shape: about n²/2. A loop whose inner part runs 1, then 2, then 3, ... up to n times is O(n²), even though it never runs the full n times on the first passes.

#Counting pairs

Back to the league. Each of the 64 teams plays the 63 others, which gives 64 × 63 = 4,032. But that counts every game twice, once from each side, so divide by 2: 2,016 games. In general, n things make n(n − 1) / 2 pairs. That is the same count you saw for the pair loop in Big-O Notation, and it is why "check every pair" is O(n²).

Ordered arrangements grow even faster. 3 people can line up in 3 × 2 × 1 = 6 orders, written 3! ("3 factorial"). 10 people have 10! = 3,628,800 orders. Any algorithm that tries every order is limited to about 10 items.

#Remainders: modulo

Six friends sit around a round table, in seats 0 to 5. A card moves 4 seats clockwise from seat 3. Where does it land? 3 + 4 = 7, but there is no seat 7. Seat 6 is seat 0 again, so seat 7 is seat 1.

That wrapping is the modulo operation, written % in both languages: the remainder after division. 7 % 6 is 1, because 7 = 1 × 6 + 1. Use it whenever something wraps around:

• Circular positions: (i + k) % n for seats, a clock, a circular buffer, days of the week.
• Even or odd: x % 2 is 0 for even numbers.
• Last digit: x % 10. Combined with dividing by 10 and rounding down, it peels off the digits of a number one at a time.
• Huge answers: problems that count ways often say "return the answer modulo 1,000,000,007". The exact number would be too big to store. Taking the remainder after each addition or multiplication gives the same final remainder as taking it once at the end.

#The code

// Halvings until n reaches 1: about log2(n)
function countHalvings(n) {
  let steps = 0;
  while (n > 1) {
    n = Math.floor(n / 2); // JS division gives decimals
    steps++;
  }
  return steps;
}
 
// 1 + 2 + ... + n, no loop needed
const sumTo = (n) => (n * (n + 1)) / 2;
 
// Move k seats around a table of n seats; k may be negative
const moveSeat = (i, k, n) => (((i + k) % n) + n) % n;
 
countHalvings(100); // 6
sumTo(100);         // 5050
moveSeat(3, 4, 6);  // 1
moveSeat(1, -3, 6); // 4

# Halvings until n reaches 1: about log2(n)
def count_halvings(n):
    steps = 0
    while n > 1:
        n //= 2  # whole-number division
        steps += 1
    return steps
 
# 1 + 2 + ... + n, no loop needed
def sum_to(n):
    return n * (n + 1) // 2
 
# Move k seats around a table of n seats; k may be negative
def move_seat(i, k, n):
    return (i + k) % n  # Python's % is never negative here
 
count_halvings(100)  # 6
sum_to(100)          # 5050
move_seat(3, 4, 6)   # 1
move_seat(1, -3, 6)  # 4

#Common mistakes

#Check yourself

#What to practise next

Try the sum formula on The Missing Exam Paper, and modulo on Rabbit Counter Wraparound. Then How to Approach a Problem puts these estimates to work in a step-by-step method for problems you have never seen.