Computer Science CS211

Understanding Time Complexity

Table 1: Comparing polynomial and exponential time complexity.
Assume a problem of size one takes 0.000001 seconds (1 microsecond).
Time Complexity Function Size n
10 20 30 40 50 60
n 0.00001 second 0.00002 second 0.00003 second 0.00004 second 0.00005 second 0.00006 second
n2 0.0001 second 0.0004 second 0.0009 second 0.0016 second 0.0025 second 0.0036 second
n3 0.001 second 0.008 second 0.027 second 0.064 second 0.125 second 0.216 second
n5 0.1 second 3.2 second 24.3 second 1.7 minutes 5.2 minutes 13.2 minutes
2n 0.001 second 1.0 second 17.9 minutes 12.7 days 35.7 years 366 centuries
3n 0.059 second 58 minutes 6.5 years 3855 centuries 2*108 centuries 1.3*1013 centuries
(from M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, New York, 1979.)

Table 2: Effect of improved technology on several polynomial and exponential time algorithms.
The following table represents the size of the largest problem instance solvable in 1 hour.
Time Complexity function With present computer With computer 100 times faster With computer 1000 times faster
n N1 100 N1 1000 N1
n2 N2 10 N2 31.6 N2
n3 N3 4.46 N3 10 N3
n5 N4 2.5 N4 3.98 N4
2n N5 N5+6.64 N5+9.97
3n N6 N6+4.19 N6+6.29
(from M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, New York, 1979.)

Exponential growth is huge even if the base is small
Comparing 2n and 3n, it looks like a smaller base is much better than a larger base. However, even a very small base still explodes if the time period is enough.

According to the CIA:
The land area on earth is about 150 million square kilometres
The population on Earth in the year 2000 was about 6000 million.
Thus the average population density was about 40 people / square kilometre.
The population growth is about 1.33% per year.

1.33% may not sound like much growth, however:
1.01331000 is approximately 550,000.
Thus by the year 3000, if the population growth continues at 1.33% per year, the average population density will be 21 people per square metre.
By the year 4000 there will be about 12 million people per square metre...