2
$\begingroup$

I am trying to compare asymptotic runtime bounds of a few algorithms presented in this research paper, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. The functions are,

$L(\alpha) = \exp(O(\log(n)^{a}(\log\log(n))^{1-\alpha}))$,

which I'd like to plot for $\alpha = 1/3, 1/4+O(1)$, and $1/4 + O(n)$,

and $O(n^{\log n})$

Where n is the bit-size of the input. ... Such a complexity is smaller than any $L(\epsilon)$ for any $\epsilon > 0$

I would like to plot each of these functions together to compare their growth. The problem is that the second function grows much faster than the first, which implies I am misinterpreting something.

So what is the correct way to interpret and compare these functions?

$\endgroup$
  • $\begingroup$ I can't tell what your question is, specifically. I don't see a question in your post (hint: a good question usually ends in a "?"). I also can't tell what specifically you are confused or unsure about. Would you like to have a go at editing the question to clarify what you're asking? $\endgroup$ – D.W. Jun 5 '15 at 1:01
  • $\begingroup$ I added a more clear question at the end. $\endgroup$ – MVTC Jun 5 '15 at 4:44
  • 1
    $\begingroup$ "which implies I am misinterpreting something" -- how so? It's clearly a faster growing function! See here. $\endgroup$ – Raphael Jun 5 '15 at 5:55
4
$\begingroup$

The confusion is that in the expression for $L(\alpha)$, $n$ is size of the field, whereas in $n^{O(\log n)}$, $n$ is the size of the input. The correct comparison is between $L(\alpha) = \exp O((\log n)^\alpha (\log\log n)^{1-\alpha})$ and $(\log n)^{O(\log\log n)} = \exp O((\log\log n)^2)$, which is indeed much smaller.

Note that your suggestion to plot $L(\alpha)$ for $\alpha = 1/4 + O(1)$ and $\alpha = 1/4 + O(n)$ doesn't make much sense; you should think of $\alpha$ as a constant. It could make sense to consider $\alpha = 1/4 + o(1)$ (or $\alpha = 1/4 + \epsilon$, where $\epsilon$ is understood to be "small"), though it's not clear how exactly you'd plot it. Indeed, there is no reason to plot, and a plot wouldn't make too much sense without knowing the hidden big O constant. In practice you just do experiments.

$\endgroup$
  • $\begingroup$ MVTC, keep in mind that $O(n^{\log n}) \neq n^{O(\log n)}$, if one interprets the latter in the common way. $\endgroup$ – Raphael Jun 5 '15 at 5:56

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.