Log In
0 votes
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
in Combinatory
edited by

2 Answers

0 votes
Number of rounds in the tournament will be half of previous round

So, recurrence relation would be, $T(n)=T\left ( \frac{n}{2} \right )+1$
0 votes

Given in the problem, 

n=2^k teams

let x be the function (in terms of n) that counts number of total rounds.

Here x is incremented by one at every time,

Hence the recurrence relation will be given as follows

x(n)=x(n/2)+1 and stopping condition is x(1)=0


Related questions