Question

For part (b),

An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following (assume low-order terms are negligible):

a. linear b. O(NlogN) c. quadratic d. cubic

Answer 1

(a) Linear:

We have,

Input Size (n) = 100

Time taken = 0.5 mS

⟹ problem size that can be solved in 1 mS = 100/0.5 = 200 problems

⟹ For Time = 1 min = 60 sec = 60 x 1000 mS = 60,000 mS

⟹ So, problem size that can be solved in 60,000 mS = 200 x 60,000

⟹ n = 12,000,000 problems

(b) O(n*log₂(n)):

We have,

Input Size (n) = 100

Time taken = 0.5 mS

Which means, c * 100 log 100 = 0.5 mS

⟹ c = 0.5/100 log₂ 100 = 0.5/664 = 0.00075 ... (1)

Now, we need to find "n" from the equation below, for 1 min = 60 sec = 60 x 1000 mS = 60,000 mS

⟹ c * n log₂(n) = 60000

But, c = 0.00075 ( from equation 1 )

⟹ 0.00075 * n log₂(n) = 60000

⟹ n log₂(n) = 60000 / 0.00075 = 80,000,000

⟹ n = 3.6685 x 10⁶ problems

(c) Quadratic:

We have,

Input Size (n) = 100

Time taken = 0.5 mS

Using quadratic equation, we have,

⟹ c * 100 * 100 = 0.5

⟹ c = 5 x 10^-5 ... (1)

Now, we need to find "n" from the equation below, for 1 min = 60 sec = 60 x 1000 mS = 60,000 mS

⟹ c x n² = 60000

But, c = 5 x 10^-5 ( from equation (1) )

⟹ n² = 60000/5 x 10^-5 = 1.2 x 10⁹

⟹ n = 34641 problems

(d) Cubic

We have,

Input Size (n) = 100

Time taken = 0.5 mS

Using cubic equation, we have,

⟹ c * 100 * 100 * 100 = 0.5

⟹ c = 5 x 10^-7 ... (1)

Now, we need to find "n" from the equation below, for 1 min = 60 sec = 60 x 1000 mS = 60,000 mS

⟹ c x n³ = 60000

But, c = 5 x 10^-7 ( from equation (1) )

⟹ n³ = 60000/5 x 10^-7 = 1.2 x 10¹¹

⟹ n = 4932.42 problems

(Thank You!!)