# Particular Use of Big O Notation

I'm reading a theorem that states "...Then for each $j$ and $\epsilon>0$, there exists $n\leq 2^{O(j/\epsilon)}$..." What exactly is the big-oh notation saying in this case? I guess it must be saying that there is a constant $K$ such that for any $j$ and $\epsilon$ there is $n \leq 2^{Kj/\epsilon}$... Is that correct? Does that match the classical use of Big O, as in, say, http://en.wikipedia.org/wiki/Big_O_notation?

The theorem I quote comes from this paper.

-

I'd say that the meaning is that $\log_2(n)=O(j/\epsilon)$. This is equivalent to your interpretation.

However, there is no need to specifically pay note to the base $2$: $a^{O(m)}=b^{O(m)}$, since $b=a^{\log_a(b)}$. The author needs something down there, but it could be any number greater than $1$.

In summary, I believe that the author is claiming that a sequence $\left\{n_{j,\epsilon}\right\}$ exists where there exists a positive constant $K$ such that $n_{j,\epsilon}\leq2^{Kj/\epsilon}$ for all $j$ and $\epsilon$. It seems likely that either $\epsilon$ depends on $j$ or that the claim is for all $\epsilon$ bounded by some constant $C$. Obviously such sequences exist, but the full statement of the theorem is making a further claim about the nature of the sequence.

-
Perhaps "for all sufficiently large $j$ and sufficiently small $\epsilon>0$". –  JeffE Mar 6 '12 at 16:13

Yes, that looks strange.

Generally one would expect it to mean that there is a function $f$ such that $n\le 2^{f(\cdots)}$ and $f$ is $O(j/\epsilon)$ -- but this raises more questions that it answers here. What is $f$ a function of? Probably either $j$ or $\epsilon$ or both. And $n$ must secretly be a function of one of these (or of some underlying variable that's not mentioned in your quote), or the entire comparison would be pointless.

The big question is which limit the authors mean the big-O notation to be used on. Without any further information, it seems one just has to guess, and select the interpretation (if any) that makes the proof of the theorem (and the applications of it, if any) make sense. One shouldn't have to do this, buf occasionally one does.

Given the variable names, my first guess would have been that $n$ is a function of $j$, and $f$ is a function of $j$ that can depend on the arbitrary constant $\epsilon$. But that cannot really be the case, because if $\epsilon$ is treated as a constant, then it is pointless to write $O(j/\epsilon)$ because constant factors are ignored.

My second guess would be that the author is confused and actually just means that $n(j)$ is $O(2^{j/\epsilon})$ for all $\epsilon$. But that doesn't really make good sense either -- then the most restrictive choice of $\epsilon$ would be large ones, which is not how that variable letter is commonly used. We could correct it to "$n(j)$ is $O(2^{\epsilon j})$ for all $\epsilon$, but that would be somewhat hard to sell as an "interpretation" of the text.

On the other hand, since the quote is from a submitted paper that apparently hasn't completed peer review, I suppose anything is possible. I have read conference submissions (in CS) that made less sense than this.

-