Orders of Magnitude
This page answers frequently asked questions about
execution times and orders of magnitude.
 Time required to do algorithm X on problem Y
 Effect of faster computers on algorithm X
 How big is 2^{n}?
 Crossover of n^{x} and 2^{n}
Time required to do algorithm X on problem Y
This table comes from "Computers and Intractability, a guide to the Theory
of NPCompleteness", Micheal R. Garey & David S. Johnson, pg 7. Across is
the number of items being operated on, down is the complexity of an algorithm
operating on that many items. Each operation takes .000001 seconds.
 10  20  30  40  50  60


n  .00001 sec  .00002 sec  .00003 sec  .00004 sec  .00005 sec  .00006 sec


n^{2}  .0001 sec  .0004 sec  .0009 sec  .0016 sec  .0025 sec  .0036 sec


n^{3}  .001 sec  .008 sec  .027 sec  .064 sec  .125 sec  .216 sec


n^{5}  .1 sec  3.2 sec  24.3 sec  1.7 min  5.2 min  13.0 min


2^{n}  .001 sec  1.0 sec  17.9 min  12.7 day  35.7 yrs  366 cen


3^{n}  .059 sec  58 min  6.5 yrs  3855 cen  2x10^{8} cen  1.3x10^{13} cen


Effect of Faster Computers on algorithm X
Here is another table from the same source, page 8. Across is the type
of computer, down is the algorithm being run, the data points are the number
of items in the largest problem that can be solved in an hour.
 Present Computer  100x faster  1000x faster


n  N1  100xN1  1000xN1


n^{2}  N2  10xN2  31.6xN2


n^{3}  N3  4.64xN3  10xN3


n^{5}  N4  2.5xN4  3.98xN4


2^{n}  N5  N5+6.64  N5+9.97


3^{n}  N6  N6+4.19  N6+6.29


How big is 2^{n}?
How long would it take to guess n bits? How long would it take to
bruteforce search through 2^{n} possibilities? How big is 2^{n}?
 2^{2}
 That's 4, the number of items a human can track simultaneously.
 2^{8}
 That's 256, the number of possible values for a byte.
 2^{13}
 That's 8192 or 8K, and it fits in the onchip cache.
 2^{16}
 65,536 is 64K, the size where MSDOS has trouble
with contiguous allocations.
 2^{32}
 4,294,967,296 is 4000 meg or 4 gig. It's the
point where 32bit counters will wrap around. It's the amount of RAM
in my current machine. countx 32 5 is a
random number test of 2^{32} 4byte values and takes 103
seconds on my 1.86GHz Intel machine.
 2^{40}
 The number of keys one must check to crack any exportable
crypto by bruteforce.
 2^{43}
 "The first experimental cryptanalysis of the Data Encryption
Standard" by Mitsuru Matsui, CRYPTO 94. Matsui used 2^{43} plaintext/ciphertext
pairs to deduce the key for DES.
 2^{44}
 The maximum length random number sequence I've
ever tested on my home machine. Took a month.
 2^{57}
 5000 MIPSyears, the number of instructions executed
in the factoring of RSA129.
See
ftp://ftp.ox.ac.uk/pub/math/rsa129/rsa129.ps.gz for more details.
RSA129 was the phrase THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE and it
was encrypted using RSA and a 429bit (129decimal digit) composite number.
 2^{79}
 Avogadro's number. The number of carbon atoms
in 12 grams of coal.
 2^{80}
 An estimate of the total number of instructions
executed by all of humanity in all of history up to 2008. According
to sci.crypt quoting Odlyzko, about 2^{72} instructions were
executed in 1993 and 1994 together. According to Moore's law,
processing power doubles every two years. So that's 2^{73}
cycles total by 1994, and add one to the exponent for every two years
since then.
 2^{96}
 The number of atoms in a cubic meter of water.
 2^{128}
 The number of possible keys for IDEA.
 2^{129}
 Instructions per second for a 1metercube nanocomputer.
If a nanotech computer has atoms packed as densely as water, each atom
occupies about 10^{10} meters. If each processor has a
million atoms and is a cube, that's 100x100x100 atoms, so each
processor is 10^{8} meters across. If processors run at the
speed of light, light travels 10^{8} meters per second, so the
processor should execute 10^{16} instructions per second. A
1cubic meter computer would contain 10^{23} processors and do
10^{39}, or 2^{129}, instructions per second.
 2^{170}
 Number of atoms in the planet. From Bruce
Schneier's "Applied Cryptography", first edition.
 2^{190}
 Number of atoms in the sun. Applied Cryptography again.
 2^{256}
 Possible 256bit (32byte) keys.
 2^{268}
 Instructions executed by a nanocomputer the
size of the sun running for a million years. 2^{190} atoms /
2^{20} atoms/processor * 10^{16} instructions/second *
3600*24*365.25*1,000,000.
 2^{512}
 Possible 512bit (64byte) keys.
256bit keys (32 bytes) are probably good enough to thwart bruteforce
search forever; 512bit keys certainly are.
Crossover for n^{x} and 2^{n}
This table shows when 2^{n} becomes bigger than
n^{x}, for various n.
2^{n}  n^{x}


2^{2}  2^{2}

2^{4}  4^{2}

2^{8}  8^{2.667}

2^{16}  16^{4}

2^{32}  32^{6.4}

2^{64}  64^{10.667}

2^{128}  128^{18.285}

2^{256}  256^{32}

2^{512}  512^{56.889}

This suggests that 2^{n} is faster than n^{11} for all problems requiring less
than 2^{64} operations (that is, all currently feasible problems).
Hash Functions and Block Ciphers
Random Number Results
Computing the HOMFLY polynomial for knots
Table of Contents