[Introduction to Algorithms, CLRS] Exercise 1.2-3

This is a solution for Introduction to Algorithms. I write this for my study purpose.

1.2-3

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:

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×12=100>21 n=2⇒100×22=400>22 n=4⇒100×42=1600>24 n=8⇒100×82=6400>28                      n=16⇒100×162=25600<216

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+162=12⇒100×122=14400>212 n=12+162=14⇒100×142=19600>214 n=14+162=15⇒100×152=22500<215

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

source: https://atekihcan.github.io/CLRS/E01.02-03/