Intro to Algorithms (chapter 1-1)

Question

Just reading this book for fun, this isn't homework.

However I am already confused on the first main assignment:

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.

What does this even mean?

The next table shows a bunch of times along one axis (1 second, 1 minute, one hour, etc), and the other axis shows different f(n) such as lg n, sqrt(n), n, etc.

I am not sure how to fill in the matrix because I can't understand the question. So if f(n) = lg n, it's asking the largest n that can be solved in, for example, 1 second, but the problem takes f(n) = lg n microseconds to solve? What does that last part even mean? I don't even know how to set up the equations / ratios to solve this problem because I literally can't even put together the meaning of the question.

My hangup is over the sentence "assuming that the algorithm to solve the problem takes f(n) microseconds" because I don't know what this refers to. The time for what algorithm to solve what problem takes f(n) microseconds? So if I call f(100) it'll take lg 100 microseconds? So I need to find some n where f(n) = lg n microseconds = 1 second?

Does this mean lg n microseconds = 1 second when lg n microseconds = 10^6 microseconds, so n = 2^(10^6)?

Answer 1

For each time T, and each function f(n), you are required to find the maximal integer n such that f(n) <= T

For example, f(n) = n^2, T=1Sec = 1000 ms:

n^2 <= 1000
n <= sqrt(1000)
n <= ~31.63 <- not an integer
n <= 31

Given any function f(n), and some time T, you are required to similarly find the maximal value of n, and fill in the table.