Theta complexity of the expression

Question

Why is the complexity of expression is given as follows?

1. $(1 + 2 + 3 + … + (n – 2) + (n – 1) + n)! = \Theta((n^2)!)$
2. $1 + 2 + 2^2 + … + 2^{n-2} + 2^{n-1} + 2^n = \Theta(2^{n + 1})$
3. $\log(1) + \log(2) + … + \log(n – 1) + \log(n) = \Theta(n \log(n))$

Answer 1

The first one is actually false. We have $1+2+...+(n-1)+n=n(n+1)/2=\Theta(n^2)$, however that does not imply that we can take a factorial on both sides. Consider the fact that $n!\neq\mathcal{O}((n-1)!)$, since the ratio is $n$ and can therefore be arbitrarily large.

For the second one, we use the geometric series formula $1+2+2^2+...+2^n=2^{n+1}-1$.

The third one is the most interesting one. I hope it is clear why $\log(1)+\log(2)+...+\log(n)=\mathcal{O}(n\log(n))$. For the other way around, we note that $\log(1)+\log(2)+...+\log(n)\geq\log(n/2)+\log(n/2+1)+...+\log(n)\geq(n/2)\log(n/2)$.