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}$$