CSC 320:

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

n² 0.0001 second 0.0004 second 0.0009 second 0.0016 second 0.0025 second 0.0036 second

n³ 0.001 second 0.008 second 0.027 second 0.064 second 0.125 second 0.216 second

n⁵ 0.1 second 3.2 second 24.3 second 1.7 minutes 5.2 minutes 13.2 minutes

2ⁿ 0.001 second 1.0 second 17.9 minutes 12.7 days 35.7 years 366 centuries

3ⁿ 0.059 second 58 minutes 6.5 years 3855 centuries 2*10⁸ centuries 1.3*10¹³ 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 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
n²	0.0001 second	0.0004 second	0.0009 second	0.0016 second	0.0025 second	0.0036 second
n³	0.001 second	0.008 second	0.027 second	0.064 second	0.125 second	0.216 second
n⁵	0.1 second	3.2 second	24.3 second	1.7 minutes	5.2 minutes	13.2 minutes
2ⁿ	0.001 second	1.0 second	17.9 minutes	12.7 days	35.7 years	366 centuries
3ⁿ	0.059 second	58 minutes	6.5 years	3855 centuries	2*10⁸ centuries	1.3*10¹³ centuries

**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
n²	N2	10 N2	31.6 N2
n³	N3	4.46 N3	10 N3
n⁵	N4	2.5 N4	3.98 N4
2ⁿ	N5	N5+6.64	N5+9.97
3ⁿ	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 2ⁿ and 3ⁿ, 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 is about 6000 million.
Thus the average population density is about 40 people / square kilometre.
The current population growth is about 1.5% per year.

1.5% may not sound like much growth, however:
1.015¹⁰⁰⁰ = 2.9 million.
Thus by the year 3000, if the population growth continues at 1.5% per year, the average population density will be 120 people per square metre.
By the year 4000 there will be 350 million people per square metre...

Copied with permission from Dr. David Poole at UBC.

Back to the notes on NP-completeness.