Question

What is the smallest value of n such that an algorithm whose running time is 100n 2 runs faster than an algorithm whose running time is 2n on the same time.

Answer 1

n = 15

Explanation:

For inputs of the value of n, the running time for the algorithm A is 100n^2 and that of B is 2^n.

If A is to run faster than B, 100n^2 must be smaller than 2^n.

Let's check from n = 1 to know the value of n that fits

n = 1

100(1)^2 > 2^1

100 > 2

n = 2

100(2)^2 > 2^2

400 > 4

n = 4

100(4)^2 > 2^4

1600 > 16

n = 8

100(8)^2 > 2^8

6400 > 2^8

n = 16

100(16)^2 < 2^16

25600 < 2^16

This implies that between n = 8 and 16, A starts to run faster than B

n = (8+16)/2 = 12

100(12)^2 > 2^12

14400 > 2^12

n = (12+16)/2 = 14

100(14)^2 > 2^14

19600 > 2^14

n = (14+16)/2

n = 15

100(15)^2 < 2^15

22500 < 2^15

At n= 15, A starts running faster than B