Hi can you please post a solution to this question httpswwwc

Hi, can you please post a solution to this question:

https://www.chegg.com/homework-help/give-example-array-n-items-maximizes-number-times-test-j-min-chapter-2.2-problem-8E-solution-9780321573513-exc

Thank you.

Solution

In merge sort, at each level of the recursion, we do the following:

1 . Split the array in half.
2 . Recursively sort each half.
3 . Use the merge algorithm to combine the two halves together.

So how many comparisons are done at each step?
Well, the divide step doesn\'t make any comparisons; it just splits the array in half.
Step 2 doesn\'t (directly) make any comparisons;
all comparisons are done by recursive calls.

In step 3, we have two arrays of size n/2 and need to merge them.
This requires only 1 comparison as the 2 subarrays are already sorted.

Hence , we can say

C(1) = 0;
C(2) = 1;   
C(4) = 2;
C(8) = 4;
.
.
C(n/2) = n/4;
.
.and so on
C(n) = 2C(n/2) = n/2 , which is O(n) and hence it is linear