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.

n = 15

Step-by-step 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