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