Orders of Growth

Ten Orders of Growth

Let's assume that your computer can perform 10,000 operations (e.g., data structure manipulations, database inserts, etc.) per second. Given algorithms that require lg n, n½, n, n2, n3, n4, n6, 2n, and n! operations to perform a given task on n items, here's how long it would take to process 10, 50, 100 and 1,000 items.

Table 1: Time required to process n items at a speed of 10,000 operations/sec using eight different algorithms.
n
10 50 100 1,000
lg n 0.0003 sec 0.0006 sec 0.0007 sec 0.0010 sec
n½ 0.0003 sec 0.0007 sec 0.0010 sec 0.0032 sec
n 0.0010 sec 0.0050 sec 0.0100 sec 0.1000 sec
n lg n 0.0033 sec 0.0282 sec 0.0664 sec 0.9966 sec
n2 0.0100 sec 0.2500 sec 1.0000 sec 100.00 sec
n3 0.1000 sec 12.500 sec 100.00 sec 1.1574 day
n4 1.0000 sec 10.427 min 2.7778 hrs 3.1710 yrs
n6 1.6667 min 18.102 day 3.1710 yrs 3171.0 cen
2n 0.1024 sec 35.702 cen 4×1016 cen 1×10166 cen
n! 362.88 sec 1×1051 cen 3×10144 cen 1×102554 cen

Note: The units above are seconds (sec), minutes (min), hours (hrs), days (day), years (yrs), and centuries (cen)!

The Explosive Growth of 2n

Table 2: Time required to process n items at a speed of 10,000 operations/sec using a 2n algorithm.
n
15 20 25 30 35 40 45
3.28 sec 1.75 min 55.9 min 1.24 days 39.8 days 3.48 yrs 1.12 cen

The Explosive Growth of n!

Table 3: Time required to process n items at a speed of 10,000 operations/sec using an n! algorithm.
n
11 12 13 14 15 16 17
1.11 hrs 13.3 hrs 7.20 days 101 days 4.15 yrs 66.3 yrs 11.3 cen