a Suppose a machine on average takes 108 seconds to execute

a) Suppose a machine on average takes 10^-8 seconds to execute a single algorithm step. What is the largest input size for which the machine will execute the algorithm in 2 seconds assuming the number of steps of the algorithm is T(n) = logn

b) For the same machine, how long will it take to run an algorithm with input of size 1000 assuming the same time complexity of T(n) = logn

Solution

Answer:

Given:

         Execution for time for single step:   =10^-8 seconds

      Time taken to run the algorithm T(n) = logn

a. Calculating input size:

T(n)* 10^-8 =2s
logn * 10^-8 =2
log n =2* 10^8
log n=200000000
n=10^100000000

Largest input size for n will be 10^200000000

b. Finding the run time:

Run time = T(n)* 10^-8
       =logn * 10^-8
       = log(1000)*10^-8
       =3*10^-8 seconds

Therefore, run time will be 3*10^-8 seconds