asymptotics - Question about $Theta$ notation

Are statements below true or false?

$(1+1/n)^n = \Theta(\log n)$

$\log \log n = o(\log n)$ Note that it is little-o, not big-O

For first statement, I thought it would have $\Theta(n^2)$ complexity so it is false, while the second statement is true. Is my assumption correct?

Answer

It is a standard exercise to show that $a_n := \left( 1+\frac1n \right)^n$ is bounded between $2$ and $3$ for all $n$. (In fact, this sequences approaches $e = 2.718\cdots$.) So $a_n = \Theta(1)$ by definition of $\Theta$. Since $\Theta$ is an equivalence relation and $1 \notin \Theta(\log n)$, it follows that $a_n \notin \Theta(\log n)$ as well.

The second statement $\log \log n = o(\log n)$ is true. There are many ways to show this; for instance: $$\log n = \exp(\log \log n) = \exp\left(\frac{1}{2} \log \log n \right)^2 \geq \left( \frac{1}{2} \log \log n \right)^2 = \frac{1}{4} (\log \log n)^2 ,$$
and $\log \log n \to \infty$ as $n \to \infty$. (I used the fact that $e^x > x$ for all $x$ in the above.)