Question

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

Answer 1

100n^2<2^n

15 satisfies this.. :)

Answer 2

Answer: 15

Explanation:

For inputs of size n, running time of algorithm A is 100n2 and of B is 2n. For A to run faster than B, 100n2 must be smaller than 2n.

Calculate: A (quadratic time complexity) will run much faster than B (exponential time complexity) for very large values of n. Let’s start checking from n=1 and go up for values of n which are power of 2.

n=1⇒ 100×1^2 = 100 > 2^1  

n=2⇒ 100×2^2 = 400 > 2^2  

n=4⇒ 100×4^2 = 1600 > 2^4  

n=8⇒ 100×8^2 = 6400 > 2^8  

n=16⇒ 100×16^2 = 25600 < 2^16

Somewhere between 8 and 16, A starts to run faster than B. Let’s do what we were doing but now we are going to try middle value of the range, repeatedly (binary search).

n=8+16/ 2 = 12⇒100×12^2=14400 > 2^12  

n=12+16/ 2=14⇒100×14^2=19600 > 2^14  

n=14+16/ 2=15⇒100×15^2=22500 < 2^15

So, at n=15, A starts to run faster than B.