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

Question

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).

Explanation / Answer

int MIN(List: A, l : Int , r : Int){
   //Base case
if (r-l == 1) // Only one element
        return A[l];

int m=(l+r)/2; // finding middle

int u = MIN(a,l,m); // minimum in left half
int v= MIN(a,m,r); // minimum in right half

if(u < v)
    return u;
else
    return v;
}

Time Complexity:
   T(n) = 2T(n/2) + Constant

   Using Master theorem: T(n) = O(n)

Please let me know in case of any issue

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.