Exercises 1.2-2

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?

Solution:

We want to find where 8n^2 = 64n lg n, this reduces to n = 8 lg n.

 n    8 lg n 

1     0
2    8
10  26.56
20  34.58
30  39.26
40  42.58
50  45.15

We see that 1 doesn't satisfy this condition but n between 10 and 40 definitely do. At 50, the equation starts to fail again. We now try values between 40 and 50 to find the exact point where it fails. This point by brute force is obtained to be at 44So we conclude that between [2,43] the insertion sort algorithm runs faster than merge sort.

Alternative 

For insertion sort to beat merge sort, the time complexity of insertion sort should be less than merge sort i.e,

  8n² < 64n lgn

  n < 8lgn

  n/8 < lgn

  2^n/8 < n

           2^n/8 – n < 0

  2≤n≤43

Ans:  2≤n≤43

for values of n where 8n^2 < 64n lg(n) This is false when n equals 1 and when n is greater than or equal to 44 so insertion sort is faster in the range [2..43].