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