Problem 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.

\[ \begin{array}{cccccccc} & \text{1 second} & \text{1 minute} & \text{1 hour} & \text{1 day} & \text{1 month} & \text{1 year} & \text{1 century} \\\\ \hline \lg n & 2^{10^6} & 2^{6 \times 10^7} & 2^{3.6 \times 10^9} & 2^{8.64 \times 10^{10}} & 2^{2.59 \times 10^{12}} & 2^{3.15 \times 10^{13}} & 2^{3.15 \times 10^{15}} \\\\ \sqrt n & 10^{12} & 3.6 \times 10^{15} & 1.3 \times 10^{19} & 7.46 \times 10^{21} & 6.72 \times 10^{24} & 9.95 \times 10^{26} & 9.95 \times 10^{30} \\\\ n & 10^6 & 6 \times 10^7 & 3.6 \times 10^9 & 8.64 \times 10^{10} & 2.59 \times 10^{12} & 3.15 \times 10^{13} & 3.15 \times 10^{15} \\\\ n\lg n & 6.24 \times 10^4 & 2.8 \times 10^6 & 1.33 \times 10^8 & 2.76 \times 10^9 & 7.19 \times 10^{10} & 7.98 \times 10^{11} & 6.86 \times 10^{13} \\\\ n^2 & 1000 & 7745 & 60000 & 293938 & 1609968 & 5615692 & 56156922 \\\\ n^3 & 100 & 391 & 1532 & 4420 & 13736 & 31593 & 146645 \\\\ 2^n & 19 & 25 & 31 & 36 & 41 & 44 & 51 \\\\ n! & 9 & 11 & 12 & 13 & 15 & 16 & 17 \end{array} \]