Answer:
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
