2. 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(NlogN) c. Quadratic

2. a. Linear Time taken = ( 0.5ms * 500 ) / 100 = 2.5 ms b. NlogN N= 100 Then logn = 6.65 Nlogn = 665 For 665 instructions time taken is 0.5ms And for 500log500 time taken = = ( 0.5 * 4483 ) / 665 = 3.37 ms c. Quadratic N = 100 n^2 = 10000 For 10000 instructions time taken is 0.5 ms Then for 250000 time taken = = 0.5 * 250000 / 10000 = 12.5 ms