retagged by
343 views

1 Answer

0 votes
0 votes

Although in the ques it is asked for the value of $n$ for which insertion sort beats merge sort, but solution in the image says for $n$> 43  merge sort beats insertion sort.

So, essentially we need to find $n$ such that following inequality becomes false ( because we want $n$ for which merge sort takes longer) :

$8n^{2} < 64 n\log n$        $\Rightarrow$         $n < 8\log n$

Till n=43, it is

$43 < 8 \ast \log 43$           $\Rightarrow$        $43 < 8 \ast 5.42 = 43.41$

At n=44, it is
$44 < 8 \ast \log 44$           $\Rightarrow$        $44 < 8 \ast 5.45  = 43.67$

For the last case and for all n>43 this inequality fails. Thus, merge sort performs better than insertion sort for n>43 i.e. merge sort beats insertion sort for n>43.

This question just tries to convey the fact that insertion sort is a better choice when our input size is small.

 

Answer:

Related questions

1 votes
1 votes
2 answers
1
0 votes
0 votes
2 answers
2
Arnabi asked Jan 28, 2017
626 views
2 votes
2 votes
2 answers
3
sumit goyal 1 asked Aug 9, 2017
725 views
HOW NO. OF LEVELS IS LOG N + 1 CAN ANYONE HELP ME , how to solve this and get log n + 1
2 votes
2 votes
2 answers
4
VS asked Jan 30, 2018
4,291 views
Let A,B,C,D,E are sorted sequences having length 70,74,80,85,102 respectively.They are merged into a single sequence by merging together two sequences at a time.The minim...