1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Recurrence relation problems

  1. Apr 7, 2010 #1
    14. Suppose 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.

    So the recurrence relation would be f(n)=f(n/2)+1, with n=2^k. Not sure if thats right, seems a little too easy.

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

    f(n)=f(1)+clog_bn. (Theorem 1) Since f(1)=0; (no rounds when there is a winner) and b=2 and c=1. then the answer is log_2n. did i do this right?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted