Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition:

$f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$?

It would be quite useful when establishing the complexity class of some problems. If one wants to prove that a problem is in EXPTIME for example, when establishing the complexity of some decision procedure, it is a bit annoying to carry details like $2^{O(np(1+p))}$, when we only need to know that it is exponential in $n+p$. It would be simpler to write $2^{P(n+p)}$. The last time I asked someone, he did not have the answer but had just faced the same situation and wondered also if such a notation exists.

  • 4
    $\begingroup$ What's wrong with the classic $f(n)\le poly(g(n))$? $\endgroup$
    – Shaull
    Commented Mar 7, 2013 at 17:15
  • 1
    $\begingroup$ So is it classic to write something like $2^{poly(n+p)}$? $\endgroup$
    – BastienMob
    Commented Mar 7, 2013 at 17:18
  • 7
    $\begingroup$ Or you can use $g(n)^{O(1)}$. $\endgroup$
    – Kaveh
    Commented Mar 7, 2013 at 17:28
  • 1
    $\begingroup$ If you use it a lot you can just define it once as a new function class and not repeat it. Also $\exp(n^{O(1)})$ is common. $\endgroup$
    – Kaveh
    Commented Mar 7, 2013 at 19:43
  • 8
    $\begingroup$ I think $2^{\textrm{poly}(n)}$ is commonly used notation. $\endgroup$ Commented Mar 7, 2013 at 21:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.