In this exercise we wish to develop a divide and conquer approach to finding the

Question

In this exercise we wish to develop a divide and conquer approach to finding the maximum amongst a set of n numbers.

(a) (5%) Describe, in very intuitive terms, the greatest lower bound for finding the maximum of a set of n numbers.

(b) (5%) Suggest a divide and conquer algorithm for finding the maximum of a set of n numbers. Make sure to provide your pseudo-code.

(c) (5%) Write down and solve the recurrence associated with your divide and conquer algorithm.

(d) (5%) Is your algorithm of the best asymptotic run-time? Justify your answer either way.

Explanation / Answer

a)The greatest lower bound would be O(n)..

because..to find the maximum among the given n number.. we need to check every number..

means at least comparisions would be n-1

that is why it is O(n)..

b)

pseudo code for..finding maximum using divide and conquer procedure:

int maximum(int a[],int l,int r){
   if (r-l==1) return a[l];
   int m=(l+r)/2;
   int u,v;
   u=maximum(a,l,m);//every time dividing into half
   v=maximum(a,m,r);
   if(u>v)return u;
   return v;  
}

c)reccurence relation for above problem

T(n) = 2T(n/2)+O(1)//every time we are dividing list into 2 halfs and every time constant complexity for comparison

by master theorem..

a = 2 , b=2, k = 0, p =0

a>b^k...option 1 satisfied

hence by masters theorem..

T(n)=theta(nlogab)=theta(n)

d)yes...this run time is best ..to find the maximum among the given n number.. we need to check every number..

means at least comparisions would be n-1

that is why it is O(n)..

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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