I need to find the asymptotic upper bounds in $O$ notation for $T(N)$ in two recurrences. Assuming that $T(N)$ is constant for sufficiently small $N$, I need to make the bounds as tight as possible.
$T(N) = T(N-3) + 3 \log N$
$T(N) = 2T(N/4) + \sqrt{N}$
I know I should use master theorem. I can't implement it correctly to save my life. Can someone walk me through this
$\endgroup$ 31 Answer
$\begingroup$The Master Theorem will not get you anywhere for the first one, but would for the second.
For the first, why deal with the case $n=3k$, for a start? $$\begin{align} T(3k) &= T(3(k-1))+3\log (3k) = T(3k) = T(3(k-2))+3\log (3k)+3\log (3(k-1)) \\ &\vdots \\ &= T(3)+3\sum_{\ell=0}^{k-1} \log (3(k-\ell) = T(3) + 3k\log 3 + \sum_{\ell=1}^{k} \log \ell \\ &= T(3) + 3k \log 3 + (k\log k + o(k\log k)) = k\log k + o(k\log k) \\&= n\log n + o(n \log n) = \Theta(n \log n) \end{align} $$ and then see how to extend to $n=3k+1$ or $n=3k+2$.
for the second, the Master Theorem is indeed a good approach. You have $a=2$, $b=4$ and $f(n) = \sqrt{n}$. $\log_b a = \frac{1}{2}$, so that $$f(n) \in\Theta(n^{\log_b a} \log^0 n)$$ (second case applies for "$k=0$"). This yields $T(n) \in \Theta(n^{\log_b a} \log^1 n) = \Theta(\sqrt{n} \log n)$.
For the first part, I used the fact that $$ \sum_{\ell=1}^ k \log k = (1+o(1))k\log k. $$ If you don't know how to prove it, this is a good exercise -- and follows from a comparison series-integral: $$ \sum_{\ell=1}^ k \ln k \operatorname*{\sim}_{k\to\infty} \int_1^k \ln x dx = k\ln k - k +1. $$
$\endgroup$
