Maths/Big O notation

What a cost is made of

After thiswhat you will be able to doSplit a step count into constant, linear, and quadratic terms, and predict how each term changes when the input doubles.

Questionwhat this lesson answersCost gets written as a sum of pieces, and the pieces have names. What is a piece, what does its name actually describe, and why is cutting a cost up this way the thing that lets you compare two programs at all?

Not coveredwhat this lesson leaves outWe meet only the three pieces this arc needs: one that ignores the input, one that keeps pace with it, and one that grows like the input times itself. Faster and slower shapes are named at the end and left alone.

Take a program that receives a list of ${n}$ items. Before it looks at the list, it does some setup: it opens what it needs, prepares space for its answer, and checks its settings. Suppose we count each small operation as one primitive step, and that setup always takes 20,000 of them. Then the program makes one pass through the list, doing 500 steps for each item it touches. Finally, it compares every item with every item, doing three steps for each comparison.

Those are three separate jobs in one program. At ${n = 10}$, setup costs 20,000 steps, the pass costs 5,000, and the comparison stage costs 300. At ${n = 20}$, setup is still 20,000, the pass is 10,000, and comparisons are 1,200. At ${n = 100}$, the three counts are 20,000, 50,000, and 30,000. The jobs are not merely different amounts of work. They answer growth in different ways.

Work that ignores the input

The setup happens once. It does not matter whether the list has 10 items, 20 items, or 100: the count stays at 20,000. Doubling the input from 10 to 20 changes this part by a factor of one. It is the same work before and after the list gets bigger.

A piece of a sum is called a term. Because this term does not change with ${n}$, it is called a constant term. The word constant describes its behaviour, not its value. The constant could be 20,000 steps, 2 steps, or 2 million steps. In all three cases, its response to doubling the input is still one.

Work that keeps pace with the input

The pass does one batch of 500 steps for each item. With 10 items it costs 5,000 steps. With 20 items it costs 10,000. With 100 items it costs 50,000. There is no surprise in the change from 10 to 20: twice as many items require twice as many batches of work.

This term is called a linear term. If you plot its cost against ${n}$, the points make a straight line, which is where linear gets its name. Its count is ${500n}$, so the input doubling from ${n}$ to ${2n}$ changes it from ${500n}$ to ${500(2n)}$, exactly twice as much work.

Work that pairs the input with itself

The comparison stage has a different arrangement. Each of the ${n}$ items gets compared with each of the ${n}$ items, giving ${n \mathbin{\cdot} n}$ comparison positions. Three steps at each position make its cost ${3n^2}$. At ${n = 10}$ that is 300 steps. At ${n = 20}$ it is 1,200. At ${n = 100}$ it is 30,000.

Doubling changes both dimensions of this work. There are now ${2n}$ choices for the first item and ${2n}$ choices for the second, so ${3(2n)^2 = 3(2n)(2n) = 4(3n^2)}$. The comparison stage becomes four times as large, not twice as large.

This term is called a quadratic term. The name is literal: quadratus is Latin for square, and ${n^2}$ is exactly the area of a square with side ${n}$. The comparison positions can be drawn as that square, one axis for the first item and one for the second.

The number in front

Look again at ${3n^2}$. The ${n^2}$ says what the work does when the input grows. The 3 says that there are three steps of that shape at every comparison position. The number written in front of a term is its coefficient. Here 3 is the coefficient, and ${3n^2}$ means three of the ${n^2}$ shape.

Changing a coefficient changes the size of a piece, not its shape. Replacing ${3n^2}$ with ${30n^2}$ makes every comparison count ten times larger, but doubling ${n}$ still makes it four times larger. The 500 in ${500n}$ and the 20,000 in the setup work the same way: they say how much of a shape there is. They do not change how that shape answers growth.

Put the pieces together

We can now write the cost of the whole program. Let $T(n)$ mean its total number of primitive steps. The plus signs say that all three jobs happen:

The first addend is the quadratic term, the second is the linear term, and the last is the constant term. They are all terms because they are pieces added to make the total. At ${n = 10}$, the complete count is

Why cut the cost up at all?

The sum matters because each piece keeps its own response when the input changes. A faster computer changes every number in this cost, but it changes none of those responses. The fixed setup still stays fixed when ${n}$ doubles. The one-pass work still doubles. The comparison work still quadruples. Those are facts about how the jobs are arranged, not about the speed of one machine.

That is why the pieces are worth naming. Once two programs have costs split this way, you can compare how their work reacts to a larger input even when their raw step counts change with the machine, language, or implementation. This lesson takes all three pieces seriously and discards none of them.

These three are not the only shapes. There are shapes that grow more slowly than any of the three met here, called logarithmic, and shapes that grow far faster than the quadratic one, called exponential. Both are named here and left alone.