Maths/Big O notation

What we agree to throw away

After thiswhat you will be able to doReduce a polynomial cost to its dominant growth shape, and list the finite-size information lost when lower-order terms and constant factors are discarded.

Questionwhat this lesson answersIf we agree to discard every constant factor and every lower-order term (a piece that grows more slowly than the fastest piece in the sum), what is left that still tells the truth about an algorithm, and what have we deliberately made ourselves blind to?

Not coveredwhat this lesson leaves outWe do not give the formal definition of O here. The witness constants that make "eventually" mean something precise wait behind a door.

Put two implementations of the same task on one machine and time them. You get two numbers, and perhaps a winner. Move both programs to a faster machine and both numbers change. Change the language, the compiler, the cache state, or the operating system and they change again. Those timings describe a run of a program in a setting. We want a claim about the algorithm that survives a change of machine, language, and compiler. That is why we agree to throw things away.

Suppose the total number of individual operations, called primitive steps, is ${T(n) = 3n^2 + 500n + 20000}$ when the input has ${n}$ items. The piece that grows like ${n}$ times ${n}$, called the quadratic term, could come from a nested loop. The piece that does one batch of work for each input item, called the linear term, could come from one pass over the input. The final piece could be fixed setup work done even when the input is tiny. A term is one piece added to make the count. These are not magic labels attached after the fact: they are the pieces of a count. This lesson does not derive the count. The Summing a loop door is where a nested loop earns its ${n^2}$ rather than merely being called quadratic.

At first, the expression refuses to cooperate with the story people tell about it. Put in ${n = 10}$:

The fixed setup is 20,000 of those 25,300 steps. It is about 79 percent of the run. The quadratic part is only 300 steps. If you say this algorithm is n squared at this size, you have not made a rough statement. You have replaced the thing that consumes most of the time with a thing that barely happens.

Now move to ${n = 100}$, where ${T(100) = 30000 + 50000 + 20000 = 100000}$. The largest single piece is now the linear term, at half the run. The quadratic part has climbed to 30 percent but still does not lead. An algorithm whose growth is quadratic is, at this size, mostly doing something else.

Push a little further to ${n = 200}$ and the arithmetic is ${T(200) = 120000 + 100000 + 20000 = 240000}$. The quadratic term is now exactly half the cost, the linear term is about 41.7 percent, and setup is about 8.3 percent. That is the tipping point, and it is worth naming: it is the input size at which the term we plan to keep first becomes worth as much as everything we plan to discard, combined.

At ${n = 10000}$, the same expression gives

The quadratic term is now more than 98 percent of the total. At ${n = 1000000}$, it gives

The fixed setup that was the algorithm at ten inputs is now too small to matter on the displayed scale. The linear term and setup together are about 0.017 percent. The reversal is not a rhetorical trick. The same program has changed its visible character because the question changed from one input size to a much larger one.

This is the point of throwing terms away, but it has a precise cost. We are not simplifying the truth about this program. We are making a different claim. The full expression says something about the number of steps for each input size in a chosen machine model. Keeping only ${3n^2}$ says that, as input grows, the quadratic response eventually overwhelms the linear and fixed responses. It deliberately stops speaking about small inputs. It loses everything about the fixed setup, everything about the constant 3, and therefore much of what decides which of two same-class algorithms you should actually ship.

For example, two algorithms can both have a quadratic leading term, the piece that grows fastest in this expression, while one has a much smaller constant factor, allocates less memory, fits a cache better, or takes a different path on the inputs you have. The notation will group them into the same growth class, meaning a group with the same response as input grows. That is useful when you need to know what growth will do to you, and useless when you need to choose between them for next week’s data. Big O is not a performance warranty. It is an agreement to ignore whole categories of performance evidence in return for a portable statement about growth.

There are two acts of disposal here, not one. First divide the full cost by ${n^2}$:

As ${n}$ grows, the two fractions shrink, so ${\dfrac{T(n)}{n^2}}$ approaches 3. It approaches from above and never arrives: at ${n = 1000000}$ the ratio is still 3.0005. That is the first claim, and it keeps the coefficient, the number multiplying a term, intact: the cost is eventually some fixed multiple of ${n^2}$, and here that multiple is 3.

Then we discard the multiple too. Call it ${c}$, write ${n^2}$, and the second act of disposal is done. It is a separate choice from the first, and a larger one. The first said the lower-order terms stop mattering, which is a statement about arithmetic. The second says a constant factor does not change the growth class, which is a statement about what we have decided to care about. Whether ${c}$ is safe to drop is not a theorem. A ${c}$ of 3 and a ${c}$ of 300 have the same growth class and very different electricity bills.