1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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