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.
We will provide a sample solution on how to solve for a 1sec for each of the running time.
1sec = 1000millisecond = 1000000microsecond
1sec = 10^6microsecond
Solving for
lgn = 10^6
solving for
Solving for
With an initial guess of 10^6, we can use Newton-Raphson method to get a solution
Solution is: 62746.12646969076
See https://replit.com/@AleemIsiaka/nlgn-106#main.py
Solving for
n^3 = 10^6
Solving for
Solving for n!
n! =
n! = 1*2*3*4….n =
We could pick a number as a guess, and check if the value is within .
if n = 10
10! = 3628800 (> )
9! = 637120 (< )
Hence n = 9, such that
We could do same for the rest of the time, changing the time value but running similar operations for the running times.
ㅤ | 1sec | 2minute | 1hr | 1day | 1month | 1year | 1century |
ㅤ | |||||||
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ||
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ||
62746 | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ||
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ||
19 | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | |
9 | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |