Algorithmic Complexity: Help me understanding this problem

This is the problem taken from TH Coremen, Intro to Algorithms. (that heavy book). And i don't know what author is trying to say. I am completely out of brain where to initiate this problem. :S
I spent 2+ Hours figuring.

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.

Please see this image for details :

http://postimage.org/image/uz7a9f6jf/4e7…

i beg please help.

Let's look at the first row.
The function f(n) = lg(n) says, that a problem of size n takes lg(n) ms of time to complete.
So in the column 1sec , we want to find the biggest n, so that f(n) = lg(n) <= 1s = 1000ms
We inverse lg(n)=1000 and get n = 2^1000.
So a problem of enormous size 2^1000 will only take 1000ms to calculate.

For others we might not have an inverse. But it is normally easy by trail and error.
take f(n)=n! and 1 day.
1 day = 86,400,000 ms
Plugging in a few values in a calculator gives the following numbers very fast:
11! = 39.916.800
12! = 479.001.600
So the biggest n for which we need less than a day to solve the problem is 11.

i mean programming section. -_-

Report Abuse