# How to find the Big-O of this function: $\ 2^{\log_2(n)^4}$

The definition of Big-O is $$u_n = O(v_n) \iff (\exists c \in \mathbb{R}^{*})\,\, (\exists N \in \mathbb{N}) \,\, n > N \implies u_n < c \, v_n$$

Based on that I am trying to find the upper bound for this function $$\ 2^{\log_2(n)^4}$$, but I have no idea how to continue.

It seems legit to me though that $$\ 2^{\log_2(n)^4}$$ = O($$\ 2^{\log(n)^4}$$)

Is there a way to simplify this Big-O even more? E.g could we say that O($$\ 2^{\log(n)^4}$$) = O($$\ 2^{\log(n)}$$)

• Your question is not well-defined. Since the function is in the Big-O of itself. So what exactly are you looking for? A 'simpler' function for the Big-O? Something else? – Alex Shtof Apr 2 at 13:01
• @AlexShtof Thank you for your observation. I edited my question. Yes, I am trying to find a way to simplify this even more, if thats possible. Could we say that O($\ 2^{log(n)^4}$) = O($\ 2^{log(n)}$)? – Dimitris Prasakis Apr 2 at 13:07
• @DimitrisPrasakis: no, $2^{\log n} = o(2^{(\log n)^4})$. – GEdgar Apr 2 at 13:14
• @DimitrisPrasakis No, $2^{\log_2(n)}=n$, which grows much more slowly than $2^{\log_2(n)^4}$. – kccu Apr 2 at 13:14
• Thank you everybody. – Dimitris Prasakis Apr 2 at 13:16

What they probably mean is $$\left(2^{\log_2 n}\right)^4$$. Because $$2^{\log_2 n}=n$$ this simplifies to $$n^4$$. The conventional way to read $$a^{b^c}$$ is $$a^{(b^c)}$$, which in your case would mean the function is $$2^{\left((\log_2 n)^4\right)}=n^{\left((\log_2 n)^3\right)}$$ This grows faster than any polynomial.
• It can be simplified to $n^{(\log n)^3}$, which makes it more obvious it grows faster than any polynomial. – eyeballfrog Apr 2 at 14:39