In computational complexity, we typically

count algorithms that run in a polynomial

number of steps as efficient, even though

it doesn't necessarily match up with

efficiency in practice. For example,

a polynomial like n^100 or even 1 billion

times n^2 can hardly be seen as efficient.

But it turns out that the distinction

between polynomial and exponential is

incredibly useful in practice, essentially

because polynomials don't grow that badly

as n grows. A linear polynomial scalar

multiple of n grows linearly where we use

the geometric analogy of a line.

n^2 grows like a square. n^3 grows like a

cube. In all of these cases, we can easily

draw the geometric figure corresponding

to the growth rate. But exponentials

explode. If you put 1 grain of rice on

the 1st square of a chess board, and

then on every subsequent square, you

double the number of grains of rice, this

may seem like an innocuous task, but by

the time you get to the 3rd row of the

chess board, you'll have a million grains

of rice. By the time you get to the 4th

row, you'll have a billion, and by the

time you get to the end of the chess board

you'll have 18 quintillion grains of rice.

You might also wonder: what happens when

computers get faster every year? Can't we

solve bigger problems then? It turns out

that the growth rate, exponential or

polynomial, affects this as well. So you

can do T steps in a week on your current

computer. According to Moore's Law, next

year, this will essentially be 2T. Moore's

Law may be ending, but let's pretend that

it's gonna go on forever. If you have a

problem whose running time is O of n^2, so

some constant times n^2, then doubling T

(i.e. what your computer will be able to

do next year) multiplies the size of the

problem you can solve by the square root

of 2, or around 1.4. This means that

simply by waiting for computers to get

faster, you could solve a problem that is

40% larger than the problem you could

solve today. But if the running time is

exponential (a constant times 2^n),

doubling T changes n to n + 1. You can

solve problems that are 1 bigger next year

than you could this year. This has real

implications, so let's plot some

polynomials, 2^n and n!, on a log plot.

The y axis here is the logarithm of the

number of microseconds that it takes for

an algorithm to run. If you have an

algorithm that runs in time n or n^2 or

n^3, you see that you get very similar

looking lines here. By the time n is 90 or

100, you can still solve these problems in

under a minute. But for a problem that

takes 2^n time, by the time you have

inputs of size 25 or so, you surprassed a

minute. By the time you get up to inputs

of size 80, the amount of time it takes

for this algorithm to finish is larger

than the age of the universe. For n! this

is even worse; the age of the universe is

reached by n! when n is only around 20. So

for exponential algorithms or worse, there

really is a sense in which they're

effectively impossible to use on inputs of

any reasonably large size. Note also that

because this is a log plot, if we talk

about something that's O of n^3, that

means it's at most C times n^3, that

simply shifts the n^3 curve up by a

constant factor but doesn't change its

shape, whereas for 2^n, even if you shift

it down by a constant, all this will do is

shift up by a constant the size of the

input it takes before you reach the age of

the universe, but ONLY by a constant. In

practice, it turns out that once you have

a polynomial-time algorithm, the constants

often come down soon thereafter, turning

it into an actually effective algorithm.