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 \(2^n\) on the same machine?
For A to run faster than B, \(100n^2\) must be smaller than \(2^n\).
Calculation
Intuitively we can realize that 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\) to see where that happens.
\[\begin{alignedat}{4} &n = 1 &&\Rightarrow 100 \times 1^2 &&= 100 &&> 2^n \\ &n = 2 &&\Rightarrow 100 \times 2^2 &&= 400 &&> 2^n \\ &n = 4 &&\Rightarrow 100 \times 4^2 &&= 1600 &&> 2^n \\ &n = 8 &&\Rightarrow 100 \times 8^2 &&= 6400 &&> 2^n \\ &n = 16 &&\Rightarrow 100 \times 16^2 &&= 25600 &&< 2^n \end{alignedat}\]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 = 12 \Rightarrow 100 \times 12^2 = 14400 > 2^n \\ n = 14 \Rightarrow 100 \times 14^2 = 19600 > 2^n \\ n = 15 \Rightarrow 100 \times 15^2 = 22500 < 2^n\]So, at \(n = 15\), A starts to run faster than B.
Code
Let’s start with \(n = 2\) and go up to see for what value of \(n\) merge sort again starts to beat insertion sort.
You can run the python code in the below editor and see that for \(n = 15\) onwards the relationship reverses.