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.

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.

share|improve this question
    
Please see also here. –  Raphael Mar 7 '12 at 11:57
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Perhaps "for all sufficiently large $j$ and sufficiently small $\epsilon>0$". –  JeffE Mar 6 '12 at 16:13
add comment

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.

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.