29,210 views
64 votes
64 votes

An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

  1. At least $2n-c$ comparisons, for some constant $c$ are needed.

  2. At most $1.5n-2$ comparisons are needed.

  3. At least $n\log_2 n$ comparisons are needed

  4. None of the above

9 Answers

Best answer
173 votes
173 votes

An easier way to find it is by using Tournament Method Technique -

  1. To find the smallest element in the array will take $\mathbf{n-1}$ comparisons.
  2. To find the largest element - 
      a. After the first round of Tournament , there will be exactly  $\mathbf{n/2}$ numbers that will loose the round.
      b. So the biggest looser (the largest number) should be among these $50$ loosers.To find the largest number will take  $\mathbf{n/2 - 1}$.

Total Comparisons  $\mathbf{= (n-1) + (n/2 - 1) = 1.5n - 2}$.

Correct Answer: $B$

edited by
31 votes
31 votes

[need @arjun sir to verify it  ]

We are requested to find the MAX and MIN of the array of $n$ elements . This can be done as follws

Non Divide And Conquer

Max_Min(A,n,max,min)
  max=min=a[i]
  for i-> 2 to n
  {
      if A[i] > max   // First Comparision
         max=A[i]
      else if A[i] < min  // Seond Comparision
         min = A[i]
  }

Analysis

Best Case

When input is in increasing order

  • First Comparision : $n-1$ time
  • Second Comparision: $1$ time

Worst Case

When input is in Decreasing order

  • First Comparision : $n-1$ time
  • Second Comparision: $n-1$ time

Average Case

When First Comparision fails for half of the input

  • First Comparision : $n-1$ time
  • Second Comparision: $\frac{n}{2}$ time

 Divide And Conquer

Given a function to compute on $n$ inputs the divide-and-conquer strategy suggest splitting the inputs into $k$ distinct subsets, $1 < K \leq n$, yielding $k$ sub problems. These Sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole.

Defining the Termination condition 'SMALL' of the problem , When $n \leq 2$. In this case, the maximum and minimum are $a[i] \ \text{if} \ n = 1$ . If $n = 2$, the problem can be solved by making one comparison.

How can we Combine The Subproblem ? If $\text{MAX(A)}$ and $\text{MIN(P)}$ are the maximum and minimum of the elements of A, then $\text{MAX(A)}$ is the larger of $\text{MAX(A1)}$ and $\text{MAX(A2)}$ Similarly for $\text{MIN(A)}$

 MaxMin(i, j, max, min)
// a[1:n] is a global array. Parameters i and j are integers,   
// 1≤i≤j≤n. The effect is to set max and min to the largest and  
// smallest values in a[i:j].
{
     if (i=j) then max := min := a[i]; //Small(P)
     else if (i=j-1) then // Another case of Small(P)
          {
                if (a[i] < a[j]) then max := a[j]; min := a[i];
                else max := a[i]; min := a[j];
          }
     else
     {
           // if P is not small, divide P into sub-problems.
           // Find where to split the set.
           mid := ( i + j )/2;
           // Solve the sub-problems.
           MaxMin( i, mid, max, min );
           MaxMin( mid+1, j, max1, min1 );
           // Combine the solutions.
           if (max < max1) then max := max1;
           if (min > min1) then min := min1;
     }
}

Analysis

Time Complexity

$T(n) =\begin{Bmatrix} 0 & n=1\\ 1 & n=2\\ 2T(\frac{n}{2})+2& n>2 \end{Bmatrix}$

Using Master Theorem  Case 1 follows . Hence $T(n)$ is $\Theta(n)$

Solution

$\begin{align*} \\ T(n)&=2T(\frac{n}{2})+2\\ &=4T(\frac{n}{4})+2^{2}+2 \\ & ... \\ & = 2^{k}T(\frac{n}{2^{k}})+\sum_{i=1}^{k}2^{i} & (\text{where}\sum_{i=1}^{k}2^{i}=2^{k+1}-2)\\ &=2^{k}T(\frac{n}{2^{k}})+2^{k+1}-2 & ( \text{where,} \ k=(\log n) -1) \\ &=2^{(\log n) -1}T(1)+2^{\log n} -2 \\ &=\frac{n}{2}+n-2 \\ &=\frac{3n}{2}-2 \end{align*}$

For Input Class : Numbers in Increasing Order Non-Divide And Conquer Strategy Perform Better than Divide And Conquer

Space Complexity

   $S(n) = n+ \log n + c $ Where $n$ is the input size and $\log n$ is the size of the stack . Hence the space complexity is $O(\log n)$

Example

Consider the array

$A[] = \begin{Bmatrix}
1 &2  &3  &4  & 5 &6  &7  &8  &9 \\
 22 & 13 & -5 &-8  &15  &60  &17  &31  &47
\end{Bmatrix}$

Video Example : https://www.youtube.com/watch?v=EHRL2LbS5LU

References

  1. https://www.youtube.com/watch?v=lEvzwEcjQ54&feature=youtu.be&t=1823
  2. Cormen
  3. http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html
26 votes
26 votes

There are N number: n1, n2, n3, n4, ...... N. 

We need to find the minimum and maximum element.

Naive approach: Assign the first number with min and max, and compare every other element linearly with these min and max variable, if we found another number is minimum/maximum, we will update our min and max variable according. Every number is compared twice. Total comparison = 2(n-1) = 2n - 2.

For every number, we are doing 2 comparisons, for every two numbers, we are doing 4 comparisons, Can we reduce this?

Better Algo: Pair all the elements.

(n1, n2) , (n3, n4), (n5, n6) ..........

When N is even, for the first pair, (n1, n2) compare them with each other and find min and max. Now, from every other pair, we first compare them, and whoever is minimum among them we compare it with min, and whoever is maximum among them will be compared with max. So for every other two elements, we have three comparisons.

Total comparison = (3* (n - 2) / 2 ) + 1 (for the first pair).

= (3*n / 2 ) - 3 + 1 = 1.5*n - 2.

When N is odd, Assign the first number with min and max, and now compare them with every other pair as mentioned above.

Total comparison = 3 * (n - 1) / 2 

Reference : Cormen

edited by
10 votes
10 votes
divide and conquer gives 1.5n - 2 comparison
Answer:

Related questions

24 votes
24 votes
4 answers
1
Kathleen asked Sep 21, 2014
10,765 views
Which of the following sorting algorithms has the lowest worse-case complexity?Merge sortBubble sortQuick sortSelection sort
21 votes
21 votes
7 answers
2
pC asked Dec 21, 2015
7,772 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
36 votes
36 votes
5 answers
3
64 votes
64 votes
15 answers
4
Arjun asked Jul 6, 2016
36,697 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...