# Question: b prove that your algorithm is correct hint prove that...

###### Question details

(b) Prove that your algorithm is correct. (Hint: prove that your algorithm’s correctness follows from the correctness of another correct algorithm we already know.)

(c) Now consider the multi-slumped generalization, in which the array contains k local minima, i.e., it contains k subarrays, each of which is itself a slumped array. Let k = 2 and prove that your algorithm can fail on such an input.

(d) Suppose that k = 2 and we can guarantee that neither local minimum is closer than n/3 positions to the middle of the array, and that the “joining point” of the two singly-slumped subarrays lays in the middle third of the array. Now write an algorithm that tests A for identical adjacent values in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior.