# Is this time complexity quasi-polynomial?

I have been working in the time analysis for an algorithm and finally I got a curve that fits:

$O(2^{(\log_2(N)^{2.01})})$

N is the number of elements.

I'm right to say the above time complexity is quasi-polynomial?

• What "elements"? That is crucial here. (Also, don't use "time complexity"; you have an asymptotic upper bound.)
– Raphael
Dec 3 '14 at 11:29
• Oh, I just saw this: "I got a curve that fits" -- oh no, don't do that! What you are doing is not analysis but fortune-telling. If you want to learn about "real" algorithm analysis, you may want to head over to our reference questions on the matter.
– Raphael
Dec 3 '14 at 16:04
• @Raphael log2 = log (base 2) (i.e. Log2(32) = 5 ), N = input size (number of input elements). Dec 3 '14 at 17:57
• @Raphael I was focusing to double check the resultant time complexity. There is no curve that fits" the result is an asymptotic worst case analysis for an algorithm Dec 3 '14 at 17:59
• "input size" and "number of input elements" is not necessarily the same. Which size does each element have? Are they numbers?
– Raphael
Dec 3 '14 at 18:00

Quasi-polynomial means different things to different people, but in many contexts it means a running time of the form $O(2^{O(\log^{O(1)} N)})$, to which your example conforms.
• Is $N$ for you the size of the input (encoding), or what is it?
• $N$ is always the size of the input, unless stated otherwise. Dec 3 '14 at 15:59
• I only wish that were true. That said, note that the OP binds $N$ to be the "number of elements".