Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these notations properly. Is there any way (Lecture notes or video lectures with examples) to understand these things clearly. Thank You.

share|improve this question
1  
If the basic definitions are clear to you, then terms like $2^{O(n)}$ should make sense as well. Make sure you really understand the basics, first. See cs.stackexchange.com/q/57/157 –  Ran G. Jan 30 '13 at 7:35
    
videolectures.net/mit6046jf05_demaine_lec02 -- this was the video lecture I got help from. –  Rishi Prakash Jan 30 '13 at 10:45
3  
$O(d)^d$ is a weird one... –  Raphael Jan 30 '13 at 12:41
    
@Raphael $O(\epsilon^{1/2^n})=O(1)$, so it is weird (but correct) as well. –  Khaur Jan 30 '13 at 15:14
    
@Khaur In that case, it is (without context) not even clear whether $\varepsilon \to \infty$ or $d \to \infty$, or maybe even $\varepsilon \to 0$? –  Raphael Jan 30 '13 at 17:16

1 Answer 1

That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.

I'll start with the full syntax of the big-O notation:

$$ f(n) = O(g(n)) $$

means that

$$ \exists C~\exists n_0~\forall n > n_0: f(n) \leq Cg(n). $$

So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.

Alternatively we can say $O(g(n))$ is a set of functions defined as

$$ O(g(n)) = \{ f(n) | \exists C~\exists n_0~\forall n>n_0: f(n) \leq Cg(n) \}. $$

And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.

Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. So instead we replace the big-O with a function that conforms to the big-O. Like this:

$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$

And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just

$$ c(n) = f(n)^n,\ f(n) = O(n) $$

In the set notation it makes even more sense, because

$$ g(F) = \{ g \circ f | f \ in F \} $$

where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:

$$ 2^{O(n)} = \{ 2^{f(n)} | f(n) \in O(n) \} $$

and

$$ O(n)^n = \{ f(n)^n | f(n) \in O(n) \}. $$

As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:

$$ f(n) = O(\epsilon^{1/2^n}) $$ $$ \exists C~\exists n_o~\forall n>n_0: f(n) < C\epsilon^{1/2^n} $$

(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm.

share|improve this answer
    
If you want to be formal on notation, remember that $O(g(n))$ is a class of functions, therefore $f(n)\in O(g(n))$, not $=$. Also $\epsilon^{1/2^n}$ tends to $1$ as $n$ tends to $\infty$. –  Khaur Jan 30 '13 at 15:04
    
@Khaur: Well, that's the thing; most people write $f(n) = O(g(n))$ though using $\in$ is indeed more appropriate. Fixing the value. –  Jan Hudec Jan 30 '13 at 19:40
1  
Most people do, but you are trying to explain how the formalities work here, so you should probably also use $\in$. –  Raphael Jan 30 '13 at 20:41
    
@Raphael: I'll add it; but usually the texts that use $=$, and it seems to be the more common form, define the expression as special notation and don't talk about class of functions at all. –  Jan Hudec Jan 31 '13 at 6:47
    
@JanHudec Yes, but that routinely causes problems for beginners, because they have been conditioned to view $=$ as an equivalence relation (among other things). Just browse all the questions about asymptotics... –  Raphael Jan 31 '13 at 9:39

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.