Problem 1.1
Comparison of running times
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.
| 1 second | 1 minute | 1 hour | 1 day | 1 month | 1 year | 1 century | |
|---|---|---|---|---|---|---|---|
| $ \lg{n} $ | $ 2^{10^6} $ | $ 2^{6 \cdot 10^7} $ | $ 2^{36 \cdot 10^8} $ | $ 2^{864 \cdot 10^8} $ | $ 2^{25920 \cdot 10^8} $ | $ 2^{315360 \cdot 10^8} $ | $ 2^{31556736 \cdot 10^8} $ |
| $ \sqrt{n} $ | $ 10^{12} $ | $ 36 \cdot 10^{14} $ | $ 1296 \cdot 10^{16} $ | $ 746496 \cdot 10^{16} $ | $ 6718464 \cdot 10^{18} $ | $ 994519296 \cdot 10^{18} $ | $ 995827586973696 \cdot 10^{16} $ |
| $ n $ | $ 10^6 $ | $ 6 \cdot 10^7 $ | $ 36 \cdot 10^{8} $ | $ 864 \cdot 10^{8} $ | $ 2592 \cdot 10^{9} $ | $ 31536 \cdot 10^{9} $ | $ 31556736 \cdot 10^{8} $ |
| $ n\lg{n} $ | $ 62746 $ | $ 2801417 $ | $ 133378058 $ | $ 2755147513 $ | $ 71870856404 $ | $ 797633893349 $ | $ 68654697441062 $ |
| $ n^2 $ | $ 1000 $ | $ 7745 $ | $ 60000 $ | $ 293938 $ | $ 1609968 $ | $ 5615692 $ | $ 56175382 $ |
| $ n^3 $ | $ 100 $ | $ 391 $ | $ 1532 $ | $ 4420 $ | $ 13736 $ | $ 31593 $ | $ 146677 $ |
| $ 2^n $ | $ 19 $ | $ 25 $ | $ 31 $ | $ 36 $ | $ 41 $ | $ 44 $ | $ 51 $ |
| $ n! $ | $ 9 $ | $ 11 $ | $ 12 $ | $ 13 $ | $ 15 $ | $ 16 $ | $ 17 $ |