# What is the Big O of $2^{\log \log n}$? [duplicate]

What is the Big O class of the following expression:

$$2^{\log \log n}$$

I think the Big O is $2^n$ as I assume $\log \log n$ to be $n$. Is my assumption correct?

• Do you know what $\log$ means? – Amit Kumar Gupta Jul 18 '14 at 5:31
• What have you tried towards proving your hypothesis? Also, there is no such thing as "the big O". Finally, this question requires high-school mathematics to answer (specifically, calculation laws of powers) and not computer science expertise. – Raphael Jul 18 '14 at 7:29
• Do you know what an equation is? Using the right words and the right concepts is the beginning of understanding. – babou Jul 18 '14 at 7:50
• @babou You edited the question and that automatically nominates it for reopening. – David Richerby Jul 18 '14 at 9:46
• @DavidRicherby Thanks David. I did not know. Furthermore, I was not aware it was put on hold while I was editing. This question is interesting only as a nice compendium of a variety of errors, both in substance and in style. – babou Jul 18 '14 at 9:57

The big O (or rather, a big O) of $2^{\lg\lg n}$ is $O(2^{\lg\lg n})$. It is also $O(\log n)$, assuming $\lg$ is logarithm to base 2. Both expressions are tight, in the sense that in fact $2^{\lg\lg n} = \Theta(2^{\lg\lg n}) = \Theta(\log n)$.
The morale is that any expression can function as big O. We are usually aiming at a simple expressions, which is why we use $O(n^3)$ for $2n^3 + 15n\log$, for example. There are some canonical big O expressions, such as $O(n^a\log^b n)$. That means that if your function $f$ has order of growth $\Theta(n^a\log^b n)$, then you would usually describe it this way. Under this convention, a (tight) big O of $2^{\lg\lg n}$ is $O(\log n)$.