2
$\begingroup$

$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?

  • 1
    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.2012-12-03

1 Answers 1

2

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))$.