Orders of Magnitude

This page answers frequently asked questions about execution times and orders of magnitude.

  1. Time required to do algorithm X on problem Y
  2. Effect of faster computers on algorithm X
  3. How big is 2n?
  4. Crossover of nx and 2n

Time required to do algorithm X on problem Y

This table comes from "Computers and Intractability, a guide to the Theory of NP-Completeness", 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.
102030405060
n .00001 sec.00002 sec.00003 sec.00004 sec.00005 sec.00006 sec
n2.0001 sec.0004 sec.0009 sec.0016 sec.0025 sec.0036 sec
n3.001 sec.008 sec.027 sec.064 sec.125 sec.216 sec
n5.1 sec3.2 sec24.3 sec1.7 min5.2 min13.0 min
2n.001 sec1.0 sec17.9 min12.7 day35.7 yrs366 cen
3n.059 sec58 min6.5 yrs3855 cen2x108 cen1.3x1013 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 Computer100x faster1000x faster
nN1100xN11000xN1
n2N210xN231.6xN2
n3N34.64xN310xN3
n5N42.5xN43.98xN4
2nN5N5+6.64N5+9.97
3nN6N6+4.19N6+6.29


How big is 2n?

How long would it take to guess n bits? How long would it take to brute-force search through 2n possibilities? How big is 2n?

22
That's 4, the number of items a human can track simultaneously.
28
That's 256, the number of possible values for a byte.
213
That's 8192 or 8K, and it fits in the on-chip cache.
216
65,536 is 64K, the size where MS-DOS has trouble with contiguous allocations.
232
4,294,967,296 is 4000 meg or 4 gig. It's the point where 32-bit counters will wrap around. It's the amount of RAM in my current machine. countx 32 5 is a random number test of 232 4-byte values and takes 103 seconds on my 1.86GHz Intel machine.
240
The number of keys one must check to crack any exportable crypto by brute-force.
243
"The first experimental cryptanalysis of the Data Encryption Standard" by Mitsuru Matsui, CRYPTO 94. Matsui used 243 plaintext/ciphertext pairs to deduce the key for DES.
244
The maximum length random number sequence I've ever tested on my home machine. Took a month.
257
5000 MIPS-years, the number of instructions executed in the factoring of RSA-129. See ftp://ftp.ox.ac.uk/pub/math/rsa129/rsa129.ps.gz for more details. RSA-129 was the phrase THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE and it was encrypted using RSA and a 429-bit (129-decimal digit) composite number.
279
Avogadro's number. The number of carbon atoms in 12 grams of coal.
280
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 272 instructions were executed in 1993 and 1994 together. According to Moore's law, processing power doubles every two years. So that's 273 cycles total by 1994, and add one to the exponent for every two years since then.
296
The number of atoms in a cubic meter of water.
2128
The number of possible keys for IDEA.
2129
Instructions per second for a 1-meter-cube 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 108 meters per second, so the processor should execute 1016 instructions per second. A 1-cubic meter computer would contain 1023 processors and do 1039, or 2129, instructions per second.
2170
Number of atoms in the planet. From Bruce Schneier's "Applied Cryptography", first edition.
2190
Number of atoms in the sun. Applied Cryptography again.
2256
Possible 256-bit (32-byte) keys.
2268
Instructions executed by a nanocomputer the size of the sun running for a million years. 2190 atoms / 220 atoms/processor * 1016 instructions/second * 3600*24*365.25*1,000,000.
2512
Possible 512-bit (64-byte) keys.
256-bit keys (32 bytes) are probably good enough to thwart brute-force search forever; 512-bit keys certainly are.

Crossover for nx and 2n

This table shows when 2n becomes bigger than nx, for various n.
2nnx
2222
2442
2882.667
216164
232326.4
2646410.667
212812818.285
225625632
251251256.889
This suggests that 2n is faster than n11 for all problems requiring less than 264 operations (that is, all currently feasible problems).


Hash Functions and Block Ciphers
Random Number Results
Computing the HOMFLY polynomial for knots
Table of Contents