# Big O notation for "modulo a polynomial"

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.

• What's wrong with the classic $f(n)\le poly(g(n))$? Commented Mar 7, 2013 at 17:15
• So is it classic to write something like $2^{poly(n+p)}$? Commented Mar 7, 2013 at 17:18
• Or you can use $g(n)^{O(1)}$. Commented Mar 7, 2013 at 17:28
• 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. Commented Mar 7, 2013 at 19:43
• I think $2^{\textrm{poly}(n)}$ is commonly used notation. Commented Mar 7, 2013 at 21:48