# Math Help - Recurrence Relations Problem

1. ## 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_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 $_2$n. 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.

2. 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$.

3. Originally Posted by emakarov
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))?

4. Yes, this is correct.

5. I end up with log(n)*log(logn). Can i say it is O((log(n))^2)

6. I end up with log(n)*log(logn). Can i say it is O((log(n))^2)
Yes, since $\log 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)$.