• 1

How many comparisons are required to find the maximum element in an integer array?
  • sorting
  • numberofcomparisons
  • noOfComparisons
  •   
    subscribe
  • Posted: 6 years ago
  • Edit
  • views (3573)
  • Comments (1)

Let S be a set of n integers. Assume you can perform only addition of elements of S and comparisons between sums. Under these conditions how many comparisons are required to find the maximum element of S ?

I thought that we could find the maximum element as followed:

 
max=S(1)+S(1);
k=1;
for j=2 to n
         sum=S(1)+S(j);
         if sum>max
               max=sum;
               k=j;
return S(k);


That means that ( n-1 ) comparisons are required. Is this correct??


Can you please explain (step by step with an example) how the above algorithm works to find the maximum element? - posted 6 years ago @golla

No answers have been posted for this question.
You need to Sign In to post your solution.