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.
212
That's 4096 or 4K, and it fits in the on-chip cache.
216
65,536 is 64K, the size of memory where MS-DOS starts choking.
224
16,777,216 is 16 meg, about the limit of what can be stored in RAM. My avalanche test searched through 224 hash functions in about 4 hours on a 486, choosing the best 80,000.
232
4,294,967,296 is 4000 meg or 4 gig. It's the point where 32-bit counters will wrap around. Running my random number tests on 232 values takes a couple hours.
236
My tests took 2 days to run through 236 values; that's the longest I've ever run my tests.
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.
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.
275
An estimate of the total number of instructions executed by all of humanity in all of history. From a discussion on sci.crypt a few years ago.
279
Avogadro's number. The number of carbon atoms in 12 grams of coal.
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.
2289
Overestimate of the weight of the universe, measured in hydrogen atoms. 1.6e60kg * 1000kg/gram * 6e23 (avogadro's number).
2424
Overestimate of the instructions the universe could have computed by now. Suppose each hydrogen nucleus could execute an instruction in the time it takes light to cross the nucleus. The diameter is 2.4e-15 meters, the speed of light is 3e8m/sec, and there have been 13.8e9*365.25*24*60*60=4.35e17 seconds since the birth of the universe, that's 2135 instructions per hydrogen atom.
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. Quantum computing can brute-force problems in the square root of the time of classical computing, so you could adjust that to 512-bit (64 byte) and 1024-bit (128 byte) keys to account for quantum computing.

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