I have been hearing the phrases quasipolynomial, superpolynomial and subexponential.

I think know what quasipolynomial and subexponential is. I believe these are functions respectively of form $n^{\log^c n}$ and $n^{n^{1/c}}$ for some $c>1$.

What does superpolynomial mean?

  • 1
    $\begingroup$ Google "define: superpolynomial" answers this instantly. See wikipedia. $\endgroup$ – David Richerby Dec 12 '15 at 12:20

Superpolynomial means $n^{\omega(1)}$, that is, growing faster than any polynomial. More clearly, $n^{f(n)}$ for some function $f$ satisfying $\lim_{n\to\infty} f(n) = \infty$.

  • $\begingroup$ So superpoly contains both quasipoly and subexponential? $\endgroup$ – T.... Dec 12 '15 at 19:27
  • $\begingroup$ @Turbo That's right. $\endgroup$ – Yuval Filmus Dec 12 '15 at 19:52

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.