An algorithm takes 05 ms for an input size of 100 How large

An algorithm takes 0.5 ms for an input size of 100. How large will it take for input sizes of 500, 1000, 10000, 100000, if the running time is the following: Linear O(N log N) Quadratic Cubic exponential

Solution

(i)     Linear :

That is n =100, 100 steps are required for execution.

If n = 500, 500 steps are required for execution.

Time required for 100 steps is 0.5 ms.

Time required for 500 steps =0.5*5=2.5

Time required for 1000 steps =2.5*2=5

Time required for 10000 steps =5*10=50

Time required for 100000 steps =50*10=500

(ii)    O(N log N) :

                         i.e.    N   = 100

                         N log N   = 100 log 100 = 200 steps are required for execution.

                    Now if   N   = 500, 500 log 500 = 1349 steps required for execution.

                        Now if   N   =           1000, 1000 log 1000=2000 steps required for execution.

                         Now if   N =           10000, 10000 log 10000=40000 steps required for execution.

                         Now if   N =           100000, 100000 log 100000=500000 steps required for execution.

For 200 steps time required is 0.5 ms.

Time required for 1349 steps = 3.37 ms.

Time required for 2000 steps =5 ms

Time required for 40000 steps =100 ms

Time required for 500000 steps =1250 ms

(iii)     Quadratic   :

For n = 100,     n² = 100² steps are required.

For n = 500,     n² = 500² steps are required.

For n = 1000,     n² = 1000² steps are required.

For n = 10000,     n² = 10000² steps are required.

For n = 100000,     n² = 100000² steps are required.

Time required for 100² =   10,000 steps is 0.5 ms.

Time required for 25,0000 steps is 12.5 ms.

Time required for 10,00,000 steps is 50ms

Time required for 10000² steps is 5000 ms

Time required for 100000² steps is 500000 ms

(iv)     Cubic   :

For n = 100,       n³ =   100³ steps are required.

For n = 500,       n³ =   500³ steps are required.

For n = 1000,     n³ = 1000³ steps are required.

For n = 10000,     n³ = 10000³ steps are required.

For n = 100000,     n³ = 100000³ steps are required.

Time required for 100³ steps is 0.5 ms.

Time required for 500³ steps is 62.5 ms.

Time required for 1000³ steps is 500 ms.

Time required for 10000³ steps is 500000 ms.

Time required for 100000³ steps is 500000000 ms.