What is the smallest value of such that an algorithm whose running time is runs faster than an algorithm whose running time is on the same machine?
For inputs of size , running time of algorithm A is and of B is . For A to run faster than B, must be smaller than .
Calculate: A (quadratic time complexity) will run much faster than B (exponential time complexity) for very large values of . Let’s start checking from and go up for values of which are power of .
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).
So, at , A starts to run faster than B.
Python Code: Let’s start with and go up to see for what value of merge sort again starts to beat insertion sort.