Why the Constants Get Dropped

Last timeThe Shape of the Curve

Throwing away constant factors and smaller terms is what makes the comparison portable, and it is also what makes it occasionally wrong. Both halves of that are worth holding.

The last lesson placed procedures on a ladder of shapes and ignored

everything else about them. This lesson says why that is allowed, and then

says where it stops being allowed, because both halves get used.

FIG 1What a growth statement says in full

: the true cost of the procedure on an input of size n
: the simple shape being claimed, such as n or n^2
: a constant that is never stated, which is why the claim says nothing about seconds
: a size beyond which the claim holds, which is why it says nothing about small inputs

Two things are hidden in the statement and both of them come back later in this lesson. Note also that this is a ceiling and not a description: a procedure that scans a list once satisfies this with g equal to n squared, perfectly truthfully, which is why someone saying their code is order n squared may be making a weak claim rather than a sad one. When the shape is meant exactly, the word tight is the usual signal.

FIG 2A bad shape with a small constant against a good shape with a large one

100n, the better shapen squared, the worse shape

Below a hundred items the quadratic procedure is genuinely the faster one, by as much as a hundredfold at the left edge of the plot. At a hundred they are equal. Beyond it the linear procedure pulls away and never looks back: at ten thousand items it is a hundred times faster and at a million it is ten thousand times faster. The constant decides who wins early and the shape decides who wins eventually, and since the input is the thing that grows, eventually is usually the case worth planning for. This is the whole argument for the convention, and it is also the picture to keep in mind when the convention misleads.

Why the constant goes

A factor of a hundred is not small, and the plot still ends with the linear

procedure far ahead. That is the point. A constant shifts the crossing; it

cannot remove it.

It is also the wrong thing to attribute to the procedure in the first place.

The same algorithm in C and in Python differs by a factor of around fifty,

and nobody calls those two different algorithms.

FIG 3The share each term holds as the input grows

	n squared over 2	3n	40	largest term as a share
n = 5	12.50	15.00	40.00	0.19
n = 50	1250.00	150.00	40.00	0.87
n = 1000	500000.00	3000.00	40.00	0.99
n = 1000000	500000000000.00	3000000.00	40.00	1.00

The two marked cells are the argument. At five items the leading term is under a fifth of the work and dropping the rest would be absurd; at a million it is everything, and carrying the rest would add length to the expression without changing any comparison made with it. The test for dropping a term is whether its share tends to zero, which is a statement about where this table is going rather than about any row of it. Notice that the first row is also a warning: the convention is about large inputs and says so, and the next section is about people who forget that.

Where this goes wrong

Three situations, all common.

The input never grows. A list that is always under fifty items has no large

case, so the shapes do not matter and the constants are the entire story. A

thousand such lists per second makes the constants matter even more.

The constant is not small. Some procedures with better shapes carry setup

costs so large that no realistic input reaches the crossing point. Several

matrix multiplication methods with better exponents than the schoolbook one

are never used for this reason: the input sizes where they would win do not

fit in any machine.

The shapes are equal. If two procedures are both linear, the growth statement

is silent by construction, and the only remaining instrument is measurement.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Why the Constants Get Dropped

Why the constant goes

Where this goes wrong

1 more paragraph to go

This is the reading half

Read alongside