Question

2. In class, we discussed the recursive Merge-Sort algorithm. This sorts the whole array by sorting the left side, sorting the right side, and then merging them. Write a similar recursive algorithm that finds the maximum element of an array. (Find the max of the left side, then find the maximum of the right side, then compare the two.) Write pseudo-code for this algorithm. Give the recurrence relation that describes the number of comparisons that your algorithm uses.

Answer 1

2)

PSEUDOCODE to find the max in array:
find_max(a[],l,r):
   if(l==r):
       return a[l]
   m = (l+r)/2
   left = find_max(a,l,m)//recursive calls
   right =find_max(a,m+1,r)
   if(left<right)://comparing left and right
       return right
   else:
       return left

recurrence relation to find number of comparisions:
T(n)= 2T(n/2)+1

PSEUDOCODE to find the max in array: find_max(a[1,1,5): if (l==r): return a[1] m = (1+r)/2 left = find_max(a,l,m) //recursive calls right =find_max(a,m+1,r) if(left right)://comparing left and right return right else: return left 14 recurrence relation to find number of comparisions: T(n) = 2T (n/2) + 15