When Counting Explodes

Last timeMore Things Than Places

Polynomial, exponential and factorial counts separate so violently that the gap decides what can be computed at all, and no faster machine closes it.

Every count in this course has been a number. This lesson is about what those

numbers rule out, which turns counting from arithmetic into a statement about

what can be done at all.

FIG 1Two of the three shapes, on an ordinary scale

exponential: two to the npolynomial: n cubed

The factorial is not drawn because it cannot be: at twenty items it is eighteen orders of magnitude above the top of this chart, and including it would flatten both curves shown onto the axis. Notice where the two drawn curves cross. Below about ten items the cubic is the larger of the two, so a test at that size would suggest the exponential is the cheaper option, and by twenty items the exponential is over a hundred times larger and pulling away. That crossing is why measuring a small case is not evidence about which shape you are in.

FIG 2The same sizes, as base ten logarithms of the count

	n cubed	two to the n	n factorial	feasible to enumerate?
n = 5	2.1	1.5	2.1	1.0
n = 10	3.0	3.0	6.6	1.0
n = 20	3.9	6.0	18.4	0.0
n = 30	4.4	9.0	32.4	0.0
n = 50	5.1	15.1	64.5	0.0
n = 100	6.0	30.1	157.9	0.0

Every entry is the base ten logarithm of the count, because the counts themselves cannot share a table. Read it as the number of digits. The two marked cells are the boundary: ten items make a factorial of about four million, which is six and a half digits and enumerable in a second, and twenty items make eighteen digits, which is beyond any machine. The last column answers only for the factorial. Notice the first row, where all three counts are within a factor of ten of each other, and the last, where they differ by a hundred and fifty digits. This is the logarithms course earning its place first: these quantities can only be discussed through their exponents.

The ceiling, in numbers worth remembering

A fast machine checks something like a thousand million simple possibilities a

second. A year has about three times ten to the seven seconds. So a year of

computation gets through about ten to the sixteen possibilities, and that is

the honest ceiling with a generous machine and no cleverness.

Three anchors follow from that, and they are worth memorising because they turn

a count into a decision.

Up to about ten to the twelve is routine, meaning minutes to hours. Around ten

to the sixteen is a serious project needing real hardware and patience. Beyond

about ten to the eighteen, enumeration is finished, and no budget changes that.

So the judgement is: take the logarithm of the count, compare against twelve,

sixteen and eighteen, and decide whether to write the loop at all. That is a

five second calculation and it is the most useful thing in this course.

FIG 3What a faster machine buys

step	the search	items done in a day now	with a machine a thousand times faster	what the speedup bought
1	n cubed	about 44000 items	about 440000 items	ten times the items
2	two to the n	about 46 items	about 56 items	ten more items
3	n factorial	about 18 items	about 21 items	three more items

3 steps

This is the table that ends the argument about waiting for better hardware. A polynomial search gets genuinely faster, since the items gained scale with a root of the speedup. An exponential search gains ten items for a thousandfold speedup, and a factorial search gains three. Decades of hardware progress have moved the practical boundary for exponential search from around thirty items to around fifty, and the problems people want solved have fifty thousand. This is also why an exponential method passes testing and then fails in production: the two sizes differ by more items than the next century of hardware will supply.

The three remaining moves

Once a space cannot be enumerated, there are exactly three things to do, and

the rest of the library is largely about them.

Exploit structure. Prove that most of the space cannot contain the answer and

never visit it. Finding a name in a sorted list of a million does not examine a

million entries, it examines twenty, because sortedness lets each comparison

discard half the space. That halving is the logarithm again, and it is the

single most profitable structure in computing.

Settle for good rather than best. Accept an answer that is provably within some

distance of the best one, or merely one that works, in exchange for finishing.

Most routing, packing and scheduling in production is this, and the honest

version of it always states what it gave up.

Sample. Look at a random part of the space and accept a statistical answer.

This is what training a model on a sample of data is, what a randomised

algorithm is, and what every poll is. It is also why the course on samples

exists, since a sampled answer needs a statement about how wrong it might be.

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

When Counting Explodes

The ceiling, in numbers worth remembering

The three remaining moves

1 more paragraph to go

This is the reading half

Read alongside