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