0
$\begingroup$

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)} $)

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Alex Shtof Apr 2 at 13:01
  • $\begingroup$ @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)} $)? $\endgroup$ – Dimitris Prasakis Apr 2 at 13:07
  • 1
    $\begingroup$ @DimitrisPrasakis: no, $2^{\log n} = o(2^{(\log n)^4})$. $\endgroup$ – GEdgar Apr 2 at 13:14
  • 1
    $\begingroup$ @DimitrisPrasakis No, $2^{\log_2(n)}=n$, which grows much more slowly than $2^{\log_2(n)^4}$. $\endgroup$ – kccu Apr 2 at 13:14
  • $\begingroup$ Thank you everybody. $\endgroup$ – Dimitris Prasakis Apr 2 at 13:16
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It can be simplified to $n^{(\log n)^3}$, which makes it more obvious it grows faster than any polynomial. $\endgroup$ – eyeballfrog Apr 2 at 14:39
  • $\begingroup$ @eyeballfrog: good point $\endgroup$ – Ross Millikan Apr 2 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.