For this problem consider the problem of finding the minimum element in a list of integers.

Minimum Integer in a List (MIN) Input: A[a...b] a list of integers. Output: A[i] for some a i b such that A[i] A[j] for all a j b,or if the list is empty.

Let M(A[a ...b]) represent the output of the MIN problem on input A[a ...b]. Let min(a,b) be

a simple function that returns the minimum of two elements. Let m = (a+b)/2 be the midpoint

between a and b. Let q = (a+b)/4 be the point at one quarter the distance from a to b, and let

t = (3(a+b))4 be the point at three quarters the distance from a to b.

A). Below is aself-reduction for the MIN problem. State are cursive algorithm using pseu- docode for finding the minimum element based on this self-reduction.

if a > b

M(A[a...b]) = Min(M(A[a...b1]),A[b]) if ab

B). Using the same reduction as part 1 now state are currence T(n) that expresses the worst case run time of the recursive algorithm. Find a similar recurrence in your notes and state the tight bound on T (n).