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

Question

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.

Answer 1

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$

Answer 2

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