Question

Think of an algorithm to find the maximum value in an (unsorted) array. Now, think of an algorithm to find the second largest value in the array. Which is harder to implement? Which takes more time to run (as measured by the number of comparisons performed)? Now, think of an algorithm to find the third largest value. Finally, think of an algorithm to find the middle value. Which is the most difficult of these problems to solve?

Answer 1

Let number of elements in the array be N.

Finding the max element :

This can be solved by maintaining one external variable which is initiliased with 0 initially. Let say max and iterate on the given array. Assign current value to max max < current value condition values. return max.

No of Comparisons = N-1

Finding the second largest element :

This can be solved by doing two passes on Finding the max element. First pass takes N-1 and second pass will take N-2 comparisons.

     No of Comparisons = 2N-3

Finding the third largest element :

This can be solved by doing three passes on Finding the max element. First pass takes N-1 and second pass will take N-2 comparisons and third pass will take N-3 comparison.

     No of Comparisons = N-1+N-2+N-3 = 3N-6.

Finding the middle element:

This can be solved by doing N/2 passes on Finding the max element. First pass takes N-1 and second pass will take N-2 comparisons and so on .. N/2th pass takes N-N/2-1 comparisons.

     No of Comparisons = N-1+N-2+N-3 + … N-N/2-1

  = ( 2N^2-4N ) / 4

So in terms of complexity and number of comparisons finding middle element would take time.