I saw alll the internet answers 2<= n <= 43 Without simplify the algorithm show
ID: 3662270 • Letter: I
Question
I saw alll the internet answers 2<= n <= 43
Without simplify the algorithm show me the answer when n = 15 or 16 or n = 7
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 64nlgn steps. If n=2^k and k>=0 is an integer, for which values of k does insertion sort beat merge sort?
I could not get their point how to get that answer since with 16 and 7 or any number larger than 6 merge sort beats insertion
can you explain that point by point
Explanation / Answer
Insertion sort beats merge sort when 8n^2 < 64n lg n , n < 8 lg n , 2^ n/8 < n . This is true for 2 <= n <= 43 (found by using a calculator). Therefore, we can rewrite merge sort to use insertion sort for input of size 43 or less in order to improve the running time.