How many comparisons are required to find the maximum element in an integer array?
  • sorting
  • numberofcomparisons
  • noOfComparisons
  •   
  • Posted: 2 years ago
  • Edit
  • views (2079)
  • 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 2 years ago @golla

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