Results 1 to 6 of 6

Thread: 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)+$\displaystyle clog_b$n. (Theorem 1) Since f(1)=0; (no rounds when there is a winner) and b=2 and c=1. then the answer is log$\displaystyle _2$n. did i do this right?

    22. Suppose that the function f satisfies the recurrence relation f(n)=2f($\displaystyle \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; Apr 6th 2010 at 04:13 PM.
    Follow Math Help Forum on Facebook and Google+

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

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

    Then $\displaystyle 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 $\displaystyle 2^2f(2^{2^{m-2}})+2\cdot2^m$. This easily generalizes from two to $\displaystyle k$ iterations. Then find the limit case, when $\displaystyle f(2)=1$ has to be used; you'll get an expression for $\displaystyle f(n)$ in terms of $\displaystyle 2^m$ and $\displaystyle m$, i.e., $\displaystyle \log n$ and $\displaystyle \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 $\displaystyle m = \log\log n$ instead of $\displaystyle m = \log n$. I.e., $\displaystyle n=2^{2^m}$ and $\displaystyle \log n=2^m$.

    Then $\displaystyle 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 $\displaystyle 2^2f(2^{2^{m-2}})+2\cdot2^m$. This easily generalizes from two to $\displaystyle k$ iterations. Then find the limit case, when $\displaystyle f(2)=1$ has to be used; you'll get an expression for $\displaystyle f(n)$ in terms of $\displaystyle 2^m$ and $\displaystyle m$, i.e., $\displaystyle \log n$ and $\displaystyle \log\log n$.

    Ok so that would be $\displaystyle 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 $\displaystyle 2^kf(2)+k\cdot2^k$ or $\displaystyle 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,577
    Thanks
    790
    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,577
    Thanks
    790
    I end up with log(n)*log(logn). Can i say it is O((log(n))^2)
    Yes, since $\displaystyle \log n<n$ for all $\displaystyle n>0$, $\displaystyle \log\log n<\log n$ and so $\displaystyle \log n\cdot\log\log n<(\log n)^2$. Unfortunately, $\displaystyle (\log n)^2$ is not $\displaystyle O(\log n)$, unlike $\displaystyle \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: Dec 1st 2010, 06:59 AM
  2. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 26th 2009, 01:07 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  4. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 10th 2008, 09:21 AM
  5. help with recurrence relations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Aug 11th 2008, 05:07 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum