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

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

<p>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.</p>

CC BY-SA 3.0
2013-03-07T17:15:59.970Z
What's wrong with the classic $f(n)\le poly(g(n))$?
Shaull
CC BY-SA 3.0
2013-03-07T17:18:11.683Z
So is it classic to write something like $2^{poly(n+p)}$?
BastienMob
CC BY-SA 3.0
2013-03-07T17:22:56.567Z
It has been done before... I think it's pretty standard.
Shaull
CC BY-SA 3.0
2013-03-07T17:28:43.710Z
Or you can use $g(n)^{O(1)}$.
Kaveh
CC BY-SA 3.0
2013-03-07T17:30:02.587Z
Yes but would be one more exponent than with poly... Less readable if you have to use it a lot.
BastienMob
CC BY-SA 3.0
2013-03-07T19:43:57.773Z
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.
Kaveh
CC BY-SA 3.0
2013-03-07T21:48:13.637Z
I think $2^{\textrm{poly}(n)}$ is commonly used notation.
Robin Kothari
<cc.complexity-theory><ds.algorithms><complexity-classes><notation>
Big O notation for "modulo a polynomial"
BastienMob
# Big O notation for "modulo a polynomial"

(Asked by: username_0 on 2013-03-07)

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.

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, notation
> **Comments:**
> **username_1**: What's wrong with the classic $f(n)\le poly(g(n))$?  
> **username_0**: So is it classic to write something like $2^{poly(n+p)}$?  
> **username_1**: It has been done before... I think it's pretty standard.  
> **username_2**: Or you can use $g(n)^{O(1)}$.  
> **username_0**: Yes but would be one more exponent than with poly... Less readable if you have to use it a lot.  
> **username_2**: 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.  
> **username_3**: I think $2^{\textrm{poly}(n)}$ is commonly used notation.  

---

## 0 answers

