# Is $n^{1/\log \log n} = O(1)$?

Is $$n^{1/\log \log n} = O(1)$$ ?

Suppose that $$n^{1/\log \log n} = c$$ where $$c$$ is constant.

Taking logs of both sides,

$$\frac{1}{\log \log n}\log n = \log c.$$

• Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! – Raphael Nov 26 '19 at 20:22

The function $$n^{1/\log \log n}$$ tends to infinity, since $$n^{1/\log\log n} = e^{\log n/\log\log n},$$ and $$\log n/\log \log n \longrightarrow \infty$$.

In your last step, a contradiction is reached since (by L'Hopital) $$\lim_{n\to\infty}\frac{\log n}{\log\log n}=\lim_{n\to\infty}\frac{1/n}{1/(n\log n)}=\lim_{n\to\infty}\log n$$ and $$\log$$ is unbounded.

There isn't an error. You supposed that $$n^{1/\log\log n}$$ is constant and you derived the contradiction that $$\log n/\log\log n$$ is constant. Therefore, your supposition must be false.

It would have been better to have written that $$n^{1/\log\log n}\leq c$$ for all $$n$$, since you're really trying to show that the function is bounded above by a constant, not that is constant.

We can calculate this by applying Taylor series and L'Hôpital's rule accordingly:

$$\lim_{n\to\infty}n^{\frac{1}{\log\log{n}}}\geq\lim_{n\to\infty}n^{\frac{1}{\ln\ln{n}}}=\left [ k=\ln{n}, n=e^{k} \right ]=\lim_{k\to\infty}(e^{k})^{\frac{1}{\ln{k}}}=\lim_{k\to\infty}e^{\frac{k}{\ln{k}}}=\left [ t = \frac{k}{\ln{k}} \right ]=\lim_{t\to\infty}e^{t}\geq\lim_{t\to\infty}(1 + t)=1 + \lim_{t\to\infty}t=\infty$$

As you can see it tends to infinity.

By way of contradiction, suppose $$n^{1/ \log \log n} = O(1)$$. Then, by definition of the big-O notation, there exist positive constants $$c$$ and $$n_0$$ such that $$n^{1/\log \log n} \le c$$ for all $$n \ge n_0$$. Taking log of both sides, we obtain that $$\frac{\log n}{ \log \log n}$$ is at most some constant $$c' = \log c$$ for all sufficiently large $$n$$. But this is impossible because it can be shown (for eg by L'Hopital's rule) that $$\lim_{n \rightarrow \infty} \frac{\log n}{\log \log n} = \infty$$.