Maths/Big O notation

Summing a loop

After thiswhat you will be able to doCount the exact executions of a nested loop that visits each unordered pair once, and derive n(n - 1)/2 rather than calling it n squared by inspection.

Questionwhat this lesson answersEveryone calls a nested loop quadratic before anyone counts it. If we actually count how many times the inner line runs, what number do we get, and why is the honest answer only half of n squared?

Not coveredwhat this lesson leaves outWe count one shape of loop, the one that pairs each item with the later ones. We take its closed form from a pairing picture rather than proving it holds for every n.

Suppose a program has to compare every item in a list with every item that comes after it. The first item has many later partners. The last item has none. Here is one way to write that work. The two for lines repeat work. The changing numbers i and j mark which item each repeat is looking at. Such changing position numbers are called counters. A repeated instruction controlled by for is called a loop, and here one loop sits inside the other, which is called a nested loop.

for (let i = 0; i < n; i += 1) {
  for (let j = i + 1; j < n; j += 1) {
    compare(items[i], items[j]);
  }
}

The inner counter starts at i + 1, not at zero. When i names the first item, j can name only a later one. When i moves on, pairs already compared are not revisited in the other order. The line that calls compare therefore runs once for each pair of distinct items, and never for an item paired with itself. We will count just that line. Calling every run one unit of cost is an assumption about the machine, not a discovery about the code.

Take ${n}$ to mean the actual number of items, numbered from zero through ${n - 1}$. At ${n = 1}$, i is zero and j would start at one, already beyond the list, so the inner line runs 0 times. At ${n = 2}$, the first item compares with the second and the second has nobody after it, so it runs 1 time. At ${n = 3}$, the rows of possible later partners have lengths 2, 1, and 0, giving ${2 + 1 + 0 = 3}$. At ${n = 4}$, they have lengths 3, 2, 1, and 0, giving ${3 + 2 + 1 + 0 = 6}$. The count is growing because every new item gives all earlier items one new later partner.

Ignore the initial zero for a moment and read the additions from the other end. The totals are ${1}$, then ${1 + 2 = 3}$, then ${1 + 2 + 3 = 6}$, then ${1 + 2 + 3 + 4 = 10}$. These totals run one step ahead of the loop: the total ${1 + 2 + 3 = 6}$ is the loop’s count for four items, not three. A running total made by adding the next whole number each time is called a triangular number. The name comes from the dots you can arrange in a triangle: one dot, then a row of two, then a row of three. Our loop has the same shape with one row shifted away, because its first row has ${n - 1}$ later items, not ${n}$.

There is a short expression that replaces the ever-longer addition. Such a replacement is called a closed form. Put the sum ${1 + 2 + \ldots + n}$ above the same sum in reverse order. Each column now adds to ${n + 1}$, and there are ${n}$ columns:

The two rows together are ${n(n + 1)}$, so one row is ${\dfrac{n(n + 1)}{2}}$. Written out, that is ${\dfrac{1}{2}n^2 + \dfrac{1}{2}n}$: a quadratic term with coefficient one half, plus a linear term with coefficient one half. This pairing picture explains why the triangular numbers ${1, 3, 6, 10}$ have that value. It does not establish the claim for every possible input size. The Proof by induction door names the method that closes that gap.

The code above is one row shorter than the sum that begins at 1. Its exact count is therefore

That minus sign is the cost of being precise about j = i + 1. The actual loop still has a quadratic term with coefficient one half, together with a linear term whose coefficient is negative one half. It runs about half as many times as ${n^2}$, not exactly ${n^2}$. The triangular formula that begins with 1 and ends with ${n}$ is the same picture with the indexing moved by one. Both formulas make the same large-input claim, but they are not interchangeable when you are counting a real loop.

The picture makes the half visible. Draw an ${n}$ by ${n}$ grid whose row chooses the first item and whose column chooses the second. There are ${n^2}$ choices in which first and second position matter: choosing item A then item B occupies a different place from choosing B then A. These are ordered choices. The diagonal is the line of cells where row and column choose the same item. This loop fills only the cells above that diagonal, where ${j > i}$. It leaves the diagonal empty because an item is not compared with itself, and it leaves the lower half empty because the reverse comparison has already happened.

There are ${\dfrac{n(n - 1)}{2}}$ filled cells in the square. Divide that number by ${n^2}$ to compare it with the whole square. That fraction, called a ratio, is ${\dfrac{1}{2} - \dfrac{1}{2n}}$. It rises toward one half from below. The gap that keeps it under a perfect half is ${\dfrac{n}{2}}$, which is half of the diagonal’s ${n}$ empty cells: the loop skips the whole diagonal, and half of those skipped cells are what a perfect half would have included.

Now contrast a different inner loop, one that starts at zero and walks the full range for every outer item. It has ${n}$ rows, each with ${n}$ runs, for exactly ${n \mathbin{\cdot} n = n^2}$ runs. Both loops are called quadratic because each has a term shaped like ${n^2}$. Their counts differ by a fixed multiplier, called a constant factor: the full grid does about twice as much work as the later-pair grid. The lesson on what we agree to throw away chose to stop seeing fixed multipliers. That is why calling both loops quadratic is true, and why the word hides the difference between a full square and almost half of one.