USING STRONG INDUCTION PLEASE STATE EACH PART CLEARLY AND EX

USING STRONG INDUCTION PLEASE STATE EACH PART CLEARLY AND EXPLAIN CLEARLY

Generalize your claim from the previous question to give a formula for the total number of calls to Merge-Sort (including the first) when we run Merge-Sort(A,p,r). (It will be a function of r - p.) Using strong induction, prove that your claim is correct. As with any proof by induction, you State the claim you want to prove. State and prove the base case. State the Induction hypothesis. Prove the induction step. Apply the induction principle to prove the claim you wanted.

Solution

to calculate the formula for the number of times the MergeSort sequence is called, simply look at its big-O complexity, which O(nlogn)

now, logn is for the divide part of the algorithm, and O(n) is the number of times the MergeSort is called.

Therefore, the formula = n.

now, what is n here ? n is the number of elements being merged. Now, what will be the number in terms of r and p? MergeSort(a,p,r) will have r - p + 1 indexes, hence r - p + 1 , elements!

therefore final formula is r - p + 1 !

-------------

proof by strong induction

                 MergeSort(a,p,r)

1.

the claim we want to prove is show that the number of elements to be sorted is n = r - p + 1

2.

basis step - for n = 1

\"a\" contains jjust the one element, hence it is in itself sorted.

this completes the proof of the basic step..

3.

induction hypothesis -

here we will assume that the merge sort correctly sorts 2,3,4,........k elements!

4.

proving the inductive step-

to prove this we need to show that the merge sort correctly sorts k+1 elemetns!

in the First recursive call n1 = q-p+1=(k+1)/2 <= k , then the subarray of a[p..q] is sorted.

in the second recursive call n2 = r -q = (k+1)/2 <= k , then the subarray a[q+1.....r] is sortted.

5.

since the fact that a,p,q,r fulfill the precondition of merge sort algorithm, we can safely imply that the post condition of the merge sort algorithm states that the our original array a[p.....r] is also sorted..

-----------------

thank you