Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size \(n\), insertion sort runs in \(8n^2\) steps, while merge sort runs in \(64n \lg n\) steps. For which values of \(n\) does insertion sort beat merge sort?
For insertion sort to beat merge sort for inputs of size \(n\), \(8n^2\) must be less than \(64n \lg n\).
\[\begin{alignedat}{2} & 8n^2 &&< 64n \lg n \\ \Rightarrow \, & \cancel {8n} \cdot n &&< \cancel {8n} \cdot 8\lg n \\ \Rightarrow \, & n &&< 8\lg n \\ \Rightarrow \, & n/8 &&< \lg n \\ \Rightarrow \, & 2^{n/8} &&< n \end{alignedat}\]This is not a purely polynomial equation in \(n\). To find the required range of values of \(n\), there are a few different methods we can use…
- Manually calculate the values of these expressions for different values of \(n\)
- Use Newton’s Method
- Plot these functions and find their intersections
- Write a piece of code to found the values.
For this exercise, I’ll briefly describe all of these methods but going forward I’ll mostly use calculations that can be done with scientific calculator (to help the students visiting these pages) and python codes (to help myself).
Calculation
It is obvious that insertion sort runs at quadratic time which is definitely worse than merge sort’s linearithmic time for very large values of \(n\). We know for \(n = 1\), merge sort beats insertion sort. But for values greater than that, insertion sort beats merge sort. So, we will start checking from \(n = 2\) and go up to see for what value of \(n\) merge sort again starts to beat insertion sort.
Notice that for \(n < 8\), \(2^{n/8}\) will be a fraction. So, let’s start with \(n = 8\) and check for values of \(n\) which are powers of 2.
\[\begin{alignedat}{4} &n = 8 &&\Rightarrow 2^{8/8} &&= 2 &&< n \\ &n = 16 &&\Rightarrow 2^{16/8} &&= 4 &&< n \\ &n = 32 &&\Rightarrow 2^{32/8} &&= 16 &&< n \\ &n = 64 &&\Rightarrow 2^{64/8} &&= 256 &&> n \end{alignedat}\]Note that we don’t need to continue anymore as we have found an approximate range of values for \(n\) where merge sort starts to beat insertion sort; somewhere between 32 and 64. Let’s do what we were doing but now we are going to try middle value of either range, repeatedly (or in other words, binary search, if you have been reading ahead).
\[\begin{alignedat}{2} &n = 48 \Rightarrow 2^{48/8} = 64 &&> n \\ &n = 40 \Rightarrow 2^{40/8} = 32 &&< n \\ &n = 44 \Rightarrow 2^{44/8} = 44.8 &&> n \\ &n = 42 \Rightarrow 2^{42/8} = 38.4 &&< n \\ &n = 43 \Rightarrow 2^{43/8} = 42.4 &&< n \end{alignedat}\]So, at \(n = 44\), merge sort starts to beat insertion sort again. Therefore, for \(2 \le n \le 43\), insertion sort beats merge sort.
Newton’s Method
To apply Newton’s Method of approximation, we need to ballpark two values of \(n\) on either side of the actual solution and hit-and-try for the actual one following binary search principle. This is the principle we have almost followed in the previous section but the proper process involves calculus and way too time consuming for me to write about.
Graphical Plot
Another method to find the solutions is to plot the functions \(y = 2^{x/8}\) and \(y = x\) and finding points where they intersect.
From the above graph, we can see that the plots intersect at \(n = 1.1\) and \(n = 43.56\).
Here, \(n\) is the input size so it must be an integer. So, the values of \(n\) for which insertion beats merge sort is \(2 \le n \le 43\).
Python Code
Let’s start with \(n = 2\) and go up to see for what value of \(n\) it becomes smaller than \(2^{n/8}\).
You can run the python code in the below editor and see that for \(n = 44\) onwards the relationship reverses.