Test by Bikram | Algorithms | Test 2 | Question: 21

Question

The number of comparisons required to find the maximum and minimum element in an array $A[n]$ using Divide and Conquer method is:

• A. $(3n/2)+ 2$
• B. $(3n/2) - 2$
• C. $3n$
• D. $3n/2$

Answer 1

 Tournament Method Technique -

1. To find the smallest element in the array will take total of n-1 comparisions. (Make pairs , compare them , let the winner move to the next level, keep going till you find the winner)

2. To find the largest element - 

        a.After the first round of Tournament , there will be exactly n/2 numbers that will loose the round.

        b.So the largest number should be among these numbers.To find the largest number will take n/2 - 1 comparisons.