Question

Two algorithms A1 and A2 run on the same machine. The

running time of A1 is 100 n and running time of A2 is 2n

. For

what value of n2

, A1 runs faster than A2 ? If running time of

A1 is changed to 100 n30, then what could be the possible

value of n. You can use any spreadsheet software to plot the

graph nVS A1 &A2 running time, to analyse the results.

Answer 1

Algorithm A1 :  Run time:  100 * n
Algorithm A2 : Run time :  2ⁿ

Let n = 2ˣ      =>   Log₂ n = x 

we want  the data size n such that  100 * n < 2ⁿ

=>  Log₂ (100 2ˣ) < Log₂ 2ⁿ   = n
=>  Log₂ 100 + x  < 2ˣ
=>   2ˣ - x > 6.69
let us try x = 2, 3, 4.. .It is easy to see that x is between 3 and 4.
So n is between 8 and 16.

  100 * n < 2ⁿ 
for n = 9,  we have  900 > 512
 we get  n = 10,  as   1000 < 1024..

So  for n = 10, A1 runs faster than A2.
-----------

If A1 is changed to  100 n + 30,  then
A1 will be faster than A2  for  n = 11  as
       100 *10 +30 > 2¹⁰ 
        100 * 11 + 30 < 2¹¹