Question

For each function f(n) and time t in the 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

Answer 1

First recall that a microsecond is 10^−6 seconds. Hence, one second = 10^6 microseconds, one hour = 3600000000 = 3.6 • 10^9 microseconds, one month (assume a month has 30 days) = 2592000000000 = 2.592 • 10^12 microseconds, and one century = 3110400000000000 = 3.1104 • 10^15 microseconds.

Row 1: f(n) = log n In this case, we need to determine the largest n such that log n ≤ 1000000. To solve this inequality, we need to rewrite the inequality as 2^logn ≤ 2^1000000 or n ≤ 2^1000000. Recall from lecture that 2^10 ≈ 10^3, thus we have that 2^1000000 = 2^10•100000 = (2^10)^100000 ≈ (10^3)^100000 = 10^300000. This is the result given in the textbook. For one hour, we have that n ≤ 2^3600•1000000 and thus n ≈ 10^1080000000.

Row 8: f(n) = n! For us to see that the largest sized input is 12 that can be processed within an hour when f(n) = n! one can simply, compute 12! And verify that it is less than the number of microseconds in one hour, but that 13! is greater than the number of microseconds in an hour.

Row 4: f(n) = n log n In this case, use Maple to solve equations like n log n−1000000 = 0. The Maple command for solving this equation is fsolve(n*log[2](n) - 1000000 = 0)