Would $f(n)=f(n/2)+1$ for $n={2}^{k}$ be a recurrence relation for the question above? would I also have to say $f(1)=1?$?

Jadon Melendez
2022-07-18
Answered

Suppose that there are $n={2}^{k}$ teams in an elimination tournament, where there are n/2 games in the first round, with the $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.

Would $f(n)=f(n/2)+1$ for $n={2}^{k}$ be a recurrence relation for the question above? would I also have to say $f(1)=1?$?

Would $f(n)=f(n/2)+1$ for $n={2}^{k}$ be a recurrence relation for the question above? would I also have to say $f(1)=1?$?

You can still ask an expert for help

grocbyntza

Answered 2022-07-19
Author has **25** answers

Step 1

For all recurrence relations, you will have to define the first term.

I'm not so sure about your notation with f(n)... perhaps you mean ${T}_{n}$ where n represents the nth power of 2 of the number of teams and ${T}_{n}$ is the number of rounds?

In which case, I think yes.

Step 2

So your recurrence relation would be:

${T}_{1}=0$

${T}_{n+1}={T}_{n}+1$

where:

${T}_{n}$ is the number of rounds in the tournament

${2}^{n}$ is the number of teams in the tournament.

For all recurrence relations, you will have to define the first term.

I'm not so sure about your notation with f(n)... perhaps you mean ${T}_{n}$ where n represents the nth power of 2 of the number of teams and ${T}_{n}$ is the number of rounds?

In which case, I think yes.

Step 2

So your recurrence relation would be:

${T}_{1}=0$

${T}_{n+1}={T}_{n}+1$

where:

${T}_{n}$ is the number of rounds in the tournament

${2}^{n}$ is the number of teams in the tournament.

Leila Jennings

Answered 2022-07-20
Author has **5** answers

Step 1

This is an old question, but I got a different answer so I thought I'd share it here for anyone in the future:

Each "level" of the tournament bracket has $n={2}^{k}$ teams. That means, for each level of the bracket, $\frac{n}{2}$ games are played (every two teams plays one game). So, the number of games played at a tournament is equal to the number of games played at the highest level ($\frac{n}{2}$), where there are n teams), plus the number of games played at a tournament one level smaller.

Step 2

Hence:

${T}_{1}=0$

${T}_{n}={T}_{n-1}+\frac{n}{2}$

Where ${T}_{n}$ is the number of games played in a tournament with $n={2}^{k}$ teams.

This is an old question, but I got a different answer so I thought I'd share it here for anyone in the future:

Each "level" of the tournament bracket has $n={2}^{k}$ teams. That means, for each level of the bracket, $\frac{n}{2}$ games are played (every two teams plays one game). So, the number of games played at a tournament is equal to the number of games played at the highest level ($\frac{n}{2}$), where there are n teams), plus the number of games played at a tournament one level smaller.

Step 2

Hence:

${T}_{1}=0$

${T}_{n}={T}_{n-1}+\frac{n}{2}$

Where ${T}_{n}$ is the number of games played in a tournament with $n={2}^{k}$ teams.

asked 2020-11-09

Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.

asked 2021-07-28

Let A, B, and C be sets. Show that

asked 2021-08-18

Discrete Mathematics Basics

1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where$(a,b)\in R$ if and only if

I) everyone who has visited Web page a has also visited Web page b.

II) there are no common links found on both Web page a and Web page b.

III) there is at least one common link on Web page a and Web page b.

1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where

I) everyone who has visited Web page a has also visited Web page b.

II) there are no common links found on both Web page a and Web page b.

III) there is at least one common link on Web page a and Web page b.

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.

a) the set of sophomores taking discrete mathematics in your school

b) the set of sophomores at your school who are not taking discrete mathematics

c) the set of students at your school who either are sophomores or are taking discrete mathematics

Use these symbols:$\cap \cup$

a) the set of sophomores taking discrete mathematics in your school

b) the set of sophomores at your school who are not taking discrete mathematics

c) the set of students at your school who either are sophomores or are taking discrete mathematics

Use these symbols:

asked 2022-05-12

What is $\nabla f(x,y)$ when $f(x,y)={e}^{{x}^{2}}cosy$.

asked 2021-08-14

The following advanced exercise use a generalized ratio test to determine convergence of some series that arise in particular applications, including the ratio and root test, are not powerful enough to determine their convergence.

The test states that if

then

then

Show that

For which x > 0 does the generalized ratio test imply convergence of

asked 2021-08-15

What is the largest n for which one can solve within a day using an algorithm that requires f(n) bit operations, where each bit operation is carried out in $10}^{-11$ seconds, with these functions f(n)?

a)$\mathrm{log}n$

b)$1000n$

c)$n}^{2$

a)

b)

c)