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.

Question

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.

Answer 1

I will do the first two as an example to help you do the rest. Since a second is $10^6$ microseconds. By solving an equation which relates $f(n)$ to the time we are plotting for $f(n)$ to run we can solve for the largest input $n$ that $f$ can run on within the time limit.

$1$ second:

$log(n^2) = 1,000,000 \implies n^2 = e^{1,000,000} \implies n = e^{500,000}$

$1$ minute:

$log(n^2) = 60,000,000 \implies n^2 = e^{60,000,000} \implies n = e^{30,000,000}$

the rest can be similarly done.

P.S. make sure to floor the values of n you get from these equations because n is an integer length input.