Register

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

• edited by
228 views
1 votes
1 votes

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

  1. $(3n/2)+ 2$
  2. $(3n/2) - 2$
  3. $3n$
  4. $3n/2$
• edited by
User Avatar

1 Answer

Best answer
2 votes
2 votes

 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.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
486 views
Test by Bikram | Algorithms | Test 2 | Question: 30
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15, q(2)= 0.1, q(3) = 0.05$ is: $1.65$ $1.95$ $1.8$ $2.1$
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
User Avatar
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
368 views
Test by Bikram | Algorithms | Test 2 | Question: 28
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest paths from node G are _________.
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
User Avatar
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
486 views
Test by Bikram | Algorithms | Test 2 | Question: 27
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.
User Avatar
Link Copied!