Results 1 to 6 of 6

Math Help - Recurrence Relations Problem

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    Recurrence Relations Problem

    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?

    22. Suppose that the function f satisfies the recurrence relation f(n)=2f( \sqrt{n})+logn whenever n is a perfect square greater than 1 and f(2)=1

    a. find f(16)...I got 12
    b. Find a big-o estimate for f(n). (make the substitution m=logn)
    I'm lost on this one. Don't even know how to start.
    Last edited by bfpri; April 6th 2010 at 04:13 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I think 14, 16 and 22(a) are correct.

    For 22(b) I suggest the substitution m = \log\log n instead of m = \log n. I.e., n=2^{2^m} and \log n=2^m.

    Then f(n)=f(2^{2^m})=2f(2^{2^{m-1}})+2^m=2(2f(2^{2^{m-2}})+2^{m-1})+2^m. Let's pause here: this is 2^2f(2^{2^{m-2}})+2\cdot2^m. This easily generalizes from two to k iterations. Then find the limit case, when f(2)=1 has to be used; you'll get an expression for f(n) in terms of 2^m and m, i.e., \log n and \log\log n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by emakarov View Post
    I think 14, 16 and 22(a) are correct.

    For 22(b) I suggest the substitution m = \log\log n instead of m = \log n. I.e., n=2^{2^m} and \log n=2^m.

    Then f(n)=f(2^{2^m})=2f(2^{2^{m-1}})+2^m=2(2f(2^{2^{m-2}})+2^{m-1})+2^m. Let's pause here: this is 2^2f(2^{2^{m-2}})+2\cdot2^m. This easily generalizes from two to k iterations. Then find the limit case, when f(2)=1 has to be used; you'll get an expression for f(n) in terms of 2^m and m, i.e., \log n and \log\log n.

    Ok so that would be 2^kf(2^{2^{m-k}})+k\cdot2^m. Then m would have to be k in order for it to reach the limit case. that makes 2^kf(2)+k\cdot2^k or 2^k+k\cdot2^k Am I doing this correctly? Then what is k? log(log(n))?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Yes, this is correct.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    I end up with log(n)*log(logn). Can i say it is O((log(n))^2)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I end up with log(n)*log(logn). Can i say it is O((log(n))^2)
    Yes, since \log n<n for all n>0, \log\log n<\log n and so \log n\cdot\log\log n<(\log n)^2. Unfortunately, (\log n)^2 is not O(\log n), unlike \log(n^2).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 06:59 AM
  2. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 26th 2009, 01:07 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  4. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 10th 2008, 09:21 AM
  5. help with recurrence relations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 11th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum