CLRS 3e 1.2-3

1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n²

runs faster than an algorithm whose running time is 2ⁿ on the same machine?

We need to find n such that

100n²  < 2ⁿ 

We can start trying to plot values to try and find where this starts to fail.

n              2ⁿ           100n²

1              2             100      

10            1024        10000

20            1048576  40000

We see a value of n between 10 and 20 will already tip over the equation where the exponential values will start running significantly slower than the quadratic equation.  We find this value to be at 15.    So the strength of polynomial algorithms is at display where just 15 values can make them start running significantly faster than exponential counterparts.