Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$m^{O(1)}$ denotes the set of functions $\mathbb{N} \to \mathbb{N}$ which are polynomially bounded. (Is that what is usually means?)

Now it used as follows:

$$ f(m) \leq m^{O(1)}$$

To express that $f(x)$ is polynomially bounded. Is that just sloppy notation or what is the exact semantics?

share|cite|improve this question
Pretty much all "Big O" notation is sloppy :) You can rewrite this as $\log f(m)/\log(m) = O(1)$. Note, $\leq$ with "big O" doesn't really make sense. – Thomas Andrews Dec 3 '12 at 19:10
up vote 2 down vote accepted

I have no source for this, but I was once taught the following rule: inequalities mix with Big-O notation with an implied for all for each Big-O term on the left, and an implied there exists for each Big-O term on the right. Let me explain myself with some examples.

Your inequality ($f(m) \le m^{O(1)}$) translates to "There exists a function $g(m) \in O(1)$ such that for all $m$, we have $f(m) \le m^{g(m)}$."

The inequality "$O(n) < O(n^2)$" translates to "For all functions $g(n) \in O(n)$, there exists a function $h(n) \in O(n^2)$ such that for all $n$, we have $g(n) < h(n)$."

The equality "$O(n)O(\log \, n) = O(n \log n)$" translates to "For all functions $g(n) \in O(n)$ and $h(n) \in O(\log \, n)$, there exists a function $j(n) \in O(n \log n)$ such that for all $n$, we have $g(n)h(n) = j(n)$.

I am repurposing notation here: I am using $O(n)$ to signify the set of all functions of the variable $n$ that would be classified as $O(n)$.

EDIT: Having given this more thought, this approach carries a big drawback: it implies that $O(f(n)) < O(f(n))$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.