An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assume low-order terms are negligible); a. linear
b. O(N log N)
c. quadratic
d. cubic

a) 2.5 ms

b) 3.37 ms

c) 12.5 ms

d) 62.5 ms

Explanation:

Determine how long it takes for an input size of 500

a) Linear

For an input size of 500

time taken =  ( ( 0.5 / 100 )* 500 ) ms = 2.5 ms

b) 0(N log N )

First step : determine number of instructions For an input size ( N ) = 100

Log N = 6.65

∴ N log N = 665 instructions

i.e. 665 instructions is passed during 0.5ms

For

N log N = 500

N500 =  4483 instructions

time taken = (4483 * 0.5)/665 = 3.37 ms.

c) Quadratic

lets take N = 100

N^2 = 10000 steps per 0.5 ms

For N = 500

N^2 = 250,000  steps

time taken =  (25000*0.5) / 10000 = 12.5 ms

d) cubic .

lets take N = 100

N^3 = 1,000,000 steps per 0.5 ms

hence for N = 500

N^3 = 125*10^6 steps

hence time taken = ( (125*10^6)*0.5 / 10^6) =  62.5 ms