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.

n = 1 while 100 * n * n > 2 ** n: n += 1 print("Minimum value of n for which A runs faster than B is", n)