Homework 1

From Maryville College CS Wiki
Jump to: navigation, search


Problem 1-1 from page 14-15. In blatant violation of copyright, this is reproduced below. (Cormen, Leiserson, Rivest, and Stein will never take me alive!)

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
\mathrm{lg}\ n
\sqrt{n}
n
n\ \mathrm{lg}\ n
n^2
n^3
2^n
n!