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)+$\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.

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

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

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 $\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)$.