Can Anyone Help me with this question Show an algorithm that

Can Anyone Help me with this question?

Show an algorithm that finds the smallest and the largest of n numbers using 3n/2 - 3/2 comparisons when n is odd Assume that n = 2k for some integer k > 1, design a divide-and-conquer algorithm to find both min and max elements with 3n/2 - 2 comparisons. Describe your algorithm first and then show why it takes 3n/2 - 2 comparisons.

Solution

Algorithm:

#include<stdio.h>

struct pair

{

  int min;

  int max;

};

struct pair getMinMax(int arr[], int low, int high)

{

  struct pair minmax, mml, mmr;      

  int mid;

   

  /* If there is only on element */

  if (low == high)

  {

     minmax.max = arr[low];

     minmax.min = arr[low];    

     return minmax;

  }   

   

  /* If there are two elements */

  if (high == low + 1)

  {

     if (arr[low] > arr[high])

     {

        minmax.max = arr[low];

        minmax.min = arr[high];

     }

     else

     {

        minmax.max = arr[high];

        minmax.min = arr[low];

     }

     return minmax;

  }

   

  /* If there are more than 2 elements */

  mid = (low + high)/2;

  mml = getMinMax(arr, low, mid);

  mmr = getMinMax(arr, mid+1, high);

   

  /* compare minimums of two parts*/

  if (mml.min < mmr.min)

    minmax.min = mml.min;

  else

    minmax.min = mmr.min;    

  /* compare maximums of two parts*/

  if (mml.max > mmr.max)

    minmax.max = mml.max;

  else

    minmax.max = mmr.max;    

  

  return minmax;

}

proof: