3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\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
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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

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.