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