(M) $T(n)$ = Sum of first n natural numbers = $\frac{n(n+1)}{2} = O(n^2)$
(N) $T(n) = \Theta(n) =O(n)$, third case of Master theorem
($f(n) = n = \Omega \left(n^{\log_b a+ \epsilon}\right) = \Omega \left(n^{\log_2 1 + \epsilon}\right) = \Omega\left(n^{0 + \epsilon}\right) $, satisfied for any positive $\epsilon \leq 1$. Also, $af\left(\frac{n}{b}\right) < cf(n) \implies f\left(\frac{n}{2}\right) < cf(n) \implies \frac{n}{2} < cn$, satisfied for any $c$ greater than $0.5$)
(O) $T(n) = \Theta(n \log n) = O (n \log n)$, third case of Master theorem
($f(n) = n \log n =\Omega\left(n^{\log_b a+ \epsilon}\right) = \Omega \left(n^{\log_2 1 + \epsilon}\right) = \Omega\left(n^{0.5 + \epsilon}\right) $, satisfied for positive $\epsilon = 0.5$. Also, $af\left(\frac{n}{b}\right) < cf(n) \implies f\left(\frac{n}{2}\right) < cf(n) \implies \frac{n}{2} \log \frac{n}{2} < cn \log n$, satisfied for $c = 0.5$)
(P) Like in (M), here we are adding the log of the first n natural numbers. So,
$T_n = \log 1 + \log 2 + \log 3 + \dots + \log n$
$=\log (1\times 2\times \dots \times n)$
$=\log(n!)$
$=\Theta(n \log n)$ (Stirling's Approximation)
