ch1 p sol'ns
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")$