2.3-3 State a loop invariant for the while loop of lines 12-18 of the MERGE procedure....

Transcribed Image Text:

2.3-3 State a loop invariant for the while loop of lines 12-18 of the MERGE procedure. Show how to use it, along with the while loops of lines 20-23 and 24-27, to prove that the MERGE procedure is correct. 2.3-4 Use mathematical induction to show that when n 2 is an exact power of 2, the solution of the recurrence 2 if n = 2, T(n) = 2T (n/2)+n if n > 2 is T(n) = nlgn. 2.3-3 State a loop invariant for the while loop of lines 12-18 of the MERGE procedure. Show how to use it, along with the while loops of lines 20-23 and 24-27, to prove that the MERGE procedure is correct. 2.3-4 Use mathematical induction to show that when n 2 is an exact power of 2, the solution of the recurrence 2 if n = 2, T(n) = 2T (n/2)+n if n > 2 is T(n) = nlgn.