It takes ages
Exercise 1.3
For each function f(n) and running time t in the table below, determine the largest input size that can be solved in time t for a problem that requires f(n) microseconds (\mus) to solve on an input of size n.
| \log(n) | \sqrt{n} | n | n^2 | n^3 | 2^n | |
|---|---|---|---|---|---|---|
| 1 second (10^6 \mu s) | ||||||
| 1 minute (60 seconds) | ||||||
| 1 hour (60 minutes) | ||||||
| 1 day (24 hours) | ||||||
| 1 month (30 days) | ||||||
| 1 year (365.25 days) | ||||||
| 1 century (100 years) |
In class
For some exercises, as this one, in class I’ll show how to use the Computer Algebra System SageMath to get quicky answers. (Or as an assistant to your symbolic calculations.)
As a comparison recall that it is estimated that there may be 10^{78} to 10^{82} atoms in the known universe.