Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 3 / d / ii

For natural logarithms and sufficiently large $n$, take the logarithm of the positive expression:Set $t=\log \log n$. Then $\log n=e^t$. The exponential function grows faster than $t^2$: for example, its power series gives $e^t\ge t^3/6$ for $t>0$, so $t^2/e^t\le 6/t\to 0$. In particular, eventually $(\log \log n{)}^2\le \log n$. Exponentiating yieldsFor logarithms to a fixed base $b>1$, the natural logarithm of the left side is $(\log \log n-\log \log b{)}^2/\log b$, still smaller than $\log n$ eventually. The big O notation conclusion is therefore independent of that base choice.