Register

GO Classes DPP | Algorithms | Tournament method

626 views
2 2 votes

In a tournament method with $8$ distinct elements, suppose elements are inserted in random order into the knockout tree to find max, $2^{\text {nd }} \max$. What is the probability that the second maximum element makes it to the final match?

  1. $1 / 2$
     
  2. $1 / 4$
     
  3. $4 / 7$
     
  4. $1 / 8$

2 Answers

1 1 vote



answer must be C ,

tournament method make a binary tree and compare the players and eliminate by one,

comparison take n-1 for find the max ele and (n-1) + logn -1 for second max

if we want 2nd max element to makes it to final, lets put the max element anywhere in tree bcuz max is in the final

now, we have 7 position in the tree to insert the second max ,but it should oppose with max element so,not in same branch.

if max inserted in right subtree then second max will get in left tree.Now only 4 position left for second max

so, 4/7 is correct.

• edited by
0 0 votes

There are 8 elements. initially

Max can be placed anywhere because it always wins

To reach to the final, $2^{\text {nd }}$ max should be in the opposite half of the max element

  • Fix the bracket with two halves of 4 slots each.
     
  • Place the max anywhere (8 choices). Now there are 7 remaining slots.
     
  • Of those 7, 4 are in the opposite half and 3 are in the same half.
     
  • The 2nd max must be in the opposite half to reach the final.

$\operatorname{Pr}(2$nd max reaches final $)=4 / 7$

• reshown by
Voting & Accepting an answer helps improve the community
← Previous · GO Classes DPP | Alg...Next → · GO Classes | CSE Cou...
← Previous in category · GO Classes DPP | Alg...Next in category → · Gate@Zeal Test Serie...
Position:
Show:

Related questions

1 1 vote
2 2 answers
381
381 views
GO Classes asked Sep 4, 2025
381 views
GO Classes DPP | Algorithms | Tournament method
Which of the following statement(s) is/are correct?Tournament method always requires fewer comparisons than linear scan for any $\mathrm{n}>2$ while finding the max and s...
3 3 votes
2 2 answers
463
463 views
GO Classes asked Sep 4, 2025
463 views
GO Classes DPP | Algorithms | BFS
Consider an undirected, weighted graph G with positive weights. Let a breadth-first traversal of G be done starting from a node r.Let $d(r, u), d(r, v)$ represent the len...
2 2 votes
2 2 answers
354
354 views
GO Classes asked Sep 4, 2025
354 views
GO Classes DPP | Algorithms | DFS
Consider a directed graph $G=(V, E)$, where$\mathrm{V}=\{1,2, \ldots, 40\}$ For every vertex $u$, there is an edge $(u, v)$ iff $v=2 u$ or $v=2 u+1$Suppose the adjacency ...
1 1 vote
2 2 answers
374
374 views
GO Classes asked Sep 4, 2025
374 views
GO Classes DPP | Algorithms | DFS
Consider the following undirected graph:Which of the following is/are not correct DFS traversal sequences of the above graph starting from the vertex 3 (Assume the adjace...