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 inputs of size $n$, running time of algorithm A is $100n^2$ and of B is $2^n$. For A to run faster than B, $100n^2$ must be smaller than $2^n$.

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 \Rightarrow 100 \times 1^2 = 100 > 2^1$ $n = 2 \Rightarrow 100 \times 2^2 = 400 > 2^2$ $n = 4 \Rightarrow 100 \times 4^2 = 1600 > 2^4$ $n = 8 \Rightarrow 100 \times 8^2 = 6400 > 2^8$ $% $

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 = \frac {8 + 16} 2 = 12 \Rightarrow 100 \times 12^2 = 14400 > 2^{12}$ $n = \frac {12 + 16} 2 = 14 \Rightarrow 100 \times 14^2 = 19600 > 2^{14}$ $% $

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

Python 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.