Question

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.)

Answer 1

Solution:

Given,

=>T(n) = k2^n where k is constant and n is input size

=>T(4) = 20 ms

The answer will be "1280"

Explanation:

Finding value of constant k:

=>We know that T(4) = 20 ms

Put n = 4 and T(4) = 20 ms

=>20 = k*2^4

=>20 = k*16

=>k = 5/4

Finding value of T(10):

Put n = 10

=>T(10) = k*2^10

=>T(10) = (5/4)*2^10 ms

=>T(10) = 5*2^8 ms

=>T(10) = 5*256 ms

=>T(10) = 1280 ms

I have explained each and every part with the help of statements attached to the answer above.