Question

1. Suppose the runtime of a computer program is proportional to 2^n where n is the input size.

When given an input of size 1024, suppose the runtime is 256ms. For what input size would the program have runtime of 1ms?

2. A program takes time proportional to the input size. If the program takes 36 milliseconds for input size 30, how  many milliseconds does it take for input size 10?

3. A program takes time T(n) = k2ⁿ  where k is some constant and n is the input size. The program is run twice on the same computer (so k is the same in both cases). The first run is with n = 4 and the time taken is 20 ms. The second run is with n = 10. What is the time taken for the second run, in milliseconds? (Type in just the number; don't type "ms" at the end.)

4. It's known that mergesort takes time proporitional to nlogn, where n is the array size. Now, on a given computer suppose mergesort takes 4 seconds to sort an array of size 1,000,000, how many milliseconds would you expect it to take to sort an array of size 1,000? Type in just the number; don't type "ms" at the end.

5. A program takes time proportional to the square root of the input size. If the program takes 100 ms for input size 500, how many milliseconds does it take for input size 2,000?

Answer 1

1) since run time(t) is proportional to 2^n where n is the input size.

(where c is a constant)

when n=1024 , t=256ms

when run time t=1ms then the input size is

2) since time(t) is proportional to n where n is the input size.

(c is constant)

when n=30 t=36 ms

when n=10 then

3) Same method as above

when n=4, T=20ms

when n=10

4) Time complexity of merge sort =

So time(t) where c is constant

when n=1,000,000 t=4 seconds

4=k*1,000,000 * log (1,000,000)

k*log(1000^2)=4/1,000,000

2*k*log(1000)=4/1,000,000

k*log(1000)=2/(1000^2)

k*1000*log(1000)=2/1000 seconds=(2/1000)*1000 ms= 2ms

(if u want u can find the value of k and follow the long way, I noticed that 1000^2=1,000,000 so that can be used as a shortcut to solve it)

5)

         (c is constant)

when n=500 , t=100

when n=2000

t=100*2=200ms