Information Technology Reference
In-Depth Information
Table 6.2 Times Required for Various Computer Operations
Number of Operations Required
Value
of
Nn
n
2
n
3
n
4
2
n
3
n
n
!
n
n
1
0.0000001 0.000001
0.000001
0.000001
0.000002
0.000003
0.000001
0.000001
seconds
seconds
seconds
seconds
seconds
seconds
seconds
seconds
5
0.000005
0.000025
0.000125
0.000625
0.000032
0.000243
0.00012
0.003125
seconds
seconds
seconds
seconds
seconds
seconds
seconds
seconds
10
0.00001
0.0001
0.001
0.01
0.001024
0.059049
3.6288
2.778
seconds
seconds
seconds
seconds
seconds
seconds
seconds
hours
20
0.00002
0.0004
0.008
0.16
1.04858
58.1131
7.8218 10
4
3.37 10
12
seconds
seconds
seconds
seconds
seconds
seconds
years
years
50
0.00005
0.0025
0.0125
0.625
26.1979
2.3 108
9.77 10
60
2.87 10
70
seconds
seconds
seconds
seconds
years
years
years
years
75
0.000075
0.005625
0.421875
31.6406
1.2146 10
9
1.95 10
22
1.95 10
97
1.35 10
127
seconds
seconds
seconds
seconds
years
years
years
years
100
0.000100
0.01
1.00
1.667
4.0 10
17
1.63 10
34
3.0 10
146
3.2 10
186
seconds
seconds
seconds
minutes
years
years
years
years
Notes:
1. This table assumes that the computer is capable of performing one million steps of the algorithm
per second.
2. To gain additional insight on the length of some of these times, it is worthwhile to realize that scien
tists estimate the age of the universe to be between 10 and 20 billion years ((between 1 10
10
and
2 10
10
years).
As this part of the table shows, the time for our counting in
creases as more people sign the guest log; in the last line of the table,
it takes 0.0001 seconds to examine 100 names—assuming the com
puter can examine 1 million names in a second. Clearly, this amount
of work seems manageable, and we could handle a very large num
ber of names in only a modest amount of time. We might reasonably
conclude that this solution scales up to large data sets nicely.
Class P
A general question in computing is whether a solution can be performed in a reasonable
amount of time. “When is a solution feasible?”
While the answer to this question depends upon such matters as the amount of data
present and the speed of the machines available, Table 6.2 can give us some guidance.
The linear search is an example of a problem that scales up nicely and takes only a mod
est amount of time for varioussized data sets. Looking at Table 6.2 more closely, it
would seem overly optimistic to consider a solution to be feasible if it required 2
n
, 3
n
,
n
!,
or
n
n
units of work to process
n
data items. On the other hand, solutions requiring
n
,
n
2
,
or
n
3
units of work to process
n
items might reasonably be called feasible.
