Problems

1-1

For each function (f(n)) and time (t) in the following table, determine the largest size (n) of a problem that can be solved in time (t), assuming that the algorithm to solve the problem takes (f(n)) microseconds

Sol’n

(f(n)) 1 sec 1 min 1 hr 1 day 1 mo 1 yr 1 cen
(n) (2{106}) (2^{60 10^6}) &c &c &c &c &c
() 1.0e+12 3.6e+15 1.3e+19 7.5e+21 6.7e+24 9.9e+26 9.9e+30
(n) 1.0e+06 6.0e+07 3.6e+09 8.6e+10 2.6e+12 3.2e+13 3.2e+15
(n n) 6.3e+04 2.8e+06 1.3e+08 2.8e+09 7.2e+10 8.0e+11 6.9e+13
(n^2) 1.0e+03 7.7e+03 6.0e+04 2.9e+05 1.6e+06 5.6e+06 5.6e+07
(n^3) 100 391 1.5e+03 4.4e+03 1.4e+04 3.2e+04 1.5e+05
(2^n) 19 25 31 36 41 44 51
(n!) 9 11 12 13 15 16 17

Here is the code used to generate the table:

python $snippet("collections/clrs/times.py")$