# Kenneth Rosen Edition 7th Exercise 8.3 Question 14 (Page No. 535)

113 views
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.

edited

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$

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

1
259 views
Solve the recurrence relation for the number of rounds in the tournament described in question $14.$
How many rounds are in the elimination tournament described in question $14$ when there are $32$ teams?
Give a big-O estimate for the function $f$ given below if $f$ is an increasing function. $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$
Find $f (n)$ when $n = 3k,$ where $f$ satisfies the recurrence relation $f (n) = 2f (n/3) + 4 \:\text{with}\: f (1) = 1.$