Question

Solve the recurrence relation for the number of rounds in the tournament described in Exercise 14.

Short answer

Therefore, the result is:

$f\left(n\right)={\log }_{2}n$

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply Recurrence Relation

Recurrence relation found in the previous exercise:

$f\left(n\right)=f(n/2)+1$

$f\left(1\right)=0$

Let us assume:$n=2^k$

Let us repeatedly apply the recurrence relation:

$f\left(n\right)=f\left(2^k\right)$

$f\left(n\right)=f\left(2^{k-1}\right)+1$

$f\left(n\right)=f\left(2^{k-2}\right)+2$

$f\left(n\right)=f\left(2^2\right)+(k-2)$

$f\left(n\right)=f\left(2^1\right)+(k-1)$

$f\left(n\right)=f\left(2^0\right)+k$

$f\left(n\right)=f\left(1\right)+k$

$f\left(n\right)=0+k$

$f\left(n\right)=k$

When $2^{k-1}<n⩽2^k$then there need to be rounded (since there are too many teams for $k-1$ rounds):$n=2^k\text{is equivalent with}k={\log }_{2}n$

Therefore, the result is:

$f\left(n\right)={\log }_{2}n$