0
$\begingroup$

I got these solutions and I would like to see whether I am right or not please.

The question is:

Prove asymptotic bounds for the following recursion relations. Tighter bounds will receive more marks. You may use the Master Theorem if it applies.

  1. $C(n) = 3 C(n/2) + n.$

    For this I went with case 1 of the Master Theorem and I got that $n= O(n^{0.6})m$ so that

    $$T(n) = \Theta(n^{\log_b(a)}).$$

  2. $G(n) = G(n - 1) + 1/n.$

    In order to apply the Master Theorem I rename $n = \log m$ so I got

    $$T(\log m)= T(\log(m/2)) + 1/n.$$

    At the end I got $a=1$, $b=2$, $f(n)=1/n$ so I apply the case $f(n)= O(n^{\log_b \ a}-1)$.

  3. $I(n) = I(n/2) + n/\log(n)$

    I know the difference is not polynomial and the Master Theorem does not apply and I might use the ratio $(n \log n)/(n \log_b a)$, but I could not prove it.

  • 1
    I'm really sorry for the off topic, but... wow! I can't believe there's really a master theorem! ;)2012-01-26
  • 0
    Is "1-C(n) = ..." pronounced "one minus see of en equals..."? Or do you mean "Question (1): $C(n) = 3C(n/2)+n$"?2012-02-25

1 Answers 1