# How to interpret these asymptotic runtime bounds for discrete logarithm algorithms?

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?

• 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?
– D.W.
Jun 5 '15 at 1:01
• I added a more clear question at the end.
– MVTC
Jun 5 '15 at 4:44
• "which implies I am misinterpreting something" -- how so? It's clearly a faster growing function! See here.
– Raphael
Jun 5 '15 at 5:55

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.
• MVTC, keep in mind that $O(n^{\log n}) \neq n^{O(\log n)}$, if one interprets the latter in the common way.