Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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|improve this question
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. –  Thomas Andrews Dec 3 '12 at 19:10
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.