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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ What "elements"? That is crucial here. (Also, don't use "time complexity"; you have an asymptotic upper bound.) $\endgroup$ – Raphael♦ Dec 3 '14 at 11:29
-
2$\begingroup$ 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. $\endgroup$ – Raphael♦ Dec 3 '14 at 16:04
-
$\begingroup$ @Raphael log2 = log (base 2) (i.e. Log2(32) = 5 ), N = input size (number of input elements). $\endgroup$ – Jesus Salas Dec 3 '14 at 17:57
-
$\begingroup$ @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 $\endgroup$ – Jesus Salas Dec 3 '14 at 17:59
-
1$\begingroup$ "input size" and "number of input elements" is not necessarily the same. Which size does each element have? Are they numbers? $\endgroup$ – Raphael♦ Dec 3 '14 at 18:00
|
Show 1 more comment
$\begingroup$
$\endgroup$
3
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.
answered Dec 3 '14 at 4:22
-
$\begingroup$ Is $N$ for you the size of the input (encoding), or what is it? $\endgroup$ – Raphael♦ Dec 3 '14 at 11:31
-
$\begingroup$ $N$ is always the size of the input, unless stated otherwise. $\endgroup$ – Yuval Filmus Dec 3 '14 at 15:59
-
$\begingroup$ I only wish that were true. That said, note that the OP binds $N$ to be the "number of elements". $\endgroup$ – Raphael♦ Dec 3 '14 at 16:01
