in Combinatory edited by
1,747 views
0 votes
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
by
1.7k views

2 Answers

0 votes
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
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true