Theoretical answers only No Code please Say that we want to

Theoretical answers only! No Code please.

Say that we want to find the maximum in an array A [l, 2 ..., n] of numbers. We are allowed to base our algorithm on comparison only (namely, we do not use numbers as addresses). Given an algorithm A and a partial run of A define the run by a graph. The numbers as vertices. There is an edge between A[i] and A[j] if and only if A[i] and A[j] were compared by A. Use the above to show that in order to find the maximum in A at least n-1 comparisons are required.

Solution

Let us take an array A[1,2,3,....n] with n elements.

To find a maximum element in array we have to compare A[1] and A[2] and we have to take maximum of them.

   maximum=(A[1]>A[2])?A[1]:A[2];

And then we have to compare maximum with A[3] and we have to take maximum of them.

maximum=(maximum>A[3])?maximum:A[3];

And then we have to compare maximum with A[4] and we have to take maximum of them.

maximum=(maximum>A[4])?maximum:A[4];

we have to do this process till the last element.

At the end the value in maximum is the maximum element of the array.

For comparing A[1],A[2]------- It takes 1 comparison.

For comparing (A[1],A[2]),(maximum,A[3])------ It takes 2 comparisons.

For comparing (A[1],A[2]),(maximum,A[3]),(maximum,A[4])---------- It takes 3 comparisons.

For comparing (A[1],A[2]),(maximum,A[3]),(maximum,A[4]),...............(maximum,A[k])----- It takes k-1 comparisons.

Therefore

For comparing (A[1],A[2]),(maximum,A[3]),(maximum,A[4]),...............(maximum,A[k])-----...(maximum,A[n])------- It takes n-1 comparisons.

Therefore

     To find a maximum element in an array atleast n-1 comparisons are required.