<p>I prefer teaching the original definition with quantifiers.</p>

<p>IMO, humans generally have trouble in understanding formulas and definitions with more than two alternation of quantifiers directly. Introducing new quantifiers can clarify what the definition means. Here, the last two quantifiers just mean "for all sufficiently large n", introducing this kind of quantification can help. </p>

<p>The pictures I draw for explaining these concepts match better with the quantifier versions.</p>

<p>I think the limit simplification is useful for engineering student who are only interested in computing the growth rate, but won't be as useful for computer science students. In fact, using this simplification can cause more harm than good.</p>

<p>This idea is similar to suggestion that we use the rules for computing derivatives (of polynomials, exponentiation, ..., chain rule, ...) in place of the epsilon-delta definition of it, which IMHO is not a good idea.</p>

CC BY-SA 3.0
2011-09-08T11:25:25.543Z
The eventual domination notion is also helpful: $f(x) \ll g(x)$ iff $\esits m \forall n>m f(n) < g(n)$. Now $f \in O(g)$ iff there is $c>0$ s.t. $f(x) \ll c g(x)$.
Kaveh
CC BY-SA 2.5
2010-09-27T15:44:16.700Z
2010-09-27T15:44:16.700Z
Kaveh
<p><em>Edit: Major revision in revision 3.</em></p>

<p>Since I have never taught a class, I do not think that I can claim anything convincingly about what we should teach.  Nevertheless, here are what I thought about it.</p>

<p>There are natural examples where the “limit trick” as is written cannot be applied.  For example, suppose you implement a “variable-length vector” (like vector&lt;T&gt; in C++) by using a fixed-length array with size doubling (that is, every time you are about to exceed the size of the array, you reallocate the array twice as large as now and copy all the elements).  The size <i>S</i>(<i>n</i>) of the array when we store <i>n</i> elements in the vector is the smallest power of 2 greater than or equal to <i>n</i>.  We want to say that <i>S</i>(<i>n</i>)=O(<i>n</i>), but using the “limit trick” as is written as definition would not allow us to do so because <i>S</i>(<i>n</i>)/<i>n</i> oscillates densely in the range [1,2).  The same applies to Ω() and Θ().</p>

<p>As a somewhat separate matter, when we use these notations to describe the complexity of an algorithm, I think that your definition of Ω() is sometimes inconvenient (although I guess that that definition is common).  It is more convenient to define that <i>f</i>(<i>n</i>)=Ω(<i>g</i>(<i>n</i>)) if and only if limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) &gt; 0.  This is because some problems are trivial for infinitely many values of n (such as the perfect maching problem on a graph with an odd number <i>n</i> of vertices).  The same applies to Θ() and ω().</p>

<p>Therefore, I personally find that the following definitions the most convenient to use to describe the complexity of an algorithm: for functions <i>f</i>, <i>g</i>: ℕ → ℝ<sub>&gt;0</sub>,</p>

<ul>
<li><i>f</i>(<i>n</i>)=o(<i>g</i>(<i>n</i>)) if and only if limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) = 0.  (This is equivalent to lim <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) = 0.)</li>
<li><i>f</i>(<i>n</i>)=O(<i>g</i>(<i>n</i>)) if and only if limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) &lt; ∞.</li>
<li><i>f</i>(<i>n</i>)=Θ(<i>g</i>(<i>n</i>)) if and only if 0 &lt; limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) &lt; ∞.</li>
<li><i>f</i>(<i>n</i>)=Ω(<i>g</i>(<i>n</i>)) if and only if limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) &gt; 0.  (This is equivalent to that <i>f</i>(<i>n</i>) is not o(<i>g</i>(<i>n</i>)).)</li>
<li><i>f</i>(<i>n</i>)=ω(<i>g</i>(<i>n</i>)) if and only if limsup <i>f</i>(<i>n</i>)/<i>g</i>(<i>n</i>) = ∞.  (This is equivalent to that <i>f</i>(<i>n</i>) is not O(<i>g</i>(<i>n</i>)).)</li>
</ul>

<p>or equivalently,</p>

<ul>
<li><i>f</i>(<i>n</i>)=o(<i>g</i>(<i>n</i>)) if and only if for every <i>c</i>&gt;0, for sufficiently large <i>n</i>, <i>f</i>(<i>n</i>) ≤ <i>c</i>⋅<i>g</i>(<i>n</i>).</li>
<li><i>f</i>(<i>n</i>)=O(<i>g</i>(<i>n</i>)) if and only if for some <i>c</i>&gt;0, for sufficiently large <i>n</i>, <i>f</i>(<i>n</i>) ≤ <i>c</i>⋅<i>g</i>(<i>n</i>).</li>
<li><i>f</i>(<i>n</i>)=Θ(<i>g</i>(<i>n</i>)) if and only if <i>f</i>(<i>n</i>)=O(<i>g</i>(<i>n</i>)) and <i>f</i>(<i>n</i>)=Ω(<i>g</i>(<i>n</i>)).</li>
<li><i>f</i>(<i>n</i>)=Ω(<i>g</i>(<i>n</i>)) if and only if for some <i>d</i>&gt;0, for infinitely many <i>n</i>, <i>f</i>(<i>n</i>) ≥ <i>d</i>⋅<i>g</i>(<i>n</i>).</li>
<li><i>f</i>(<i>n</i>)=ω(<i>g</i>(<i>n</i>)) if and only if for every <i>d</i>&gt;0, for infinitely many <i>n</i>, <i>f</i>(<i>n</i>) ≥ <i>d</i>⋅<i>g</i>(<i>n</i>).</li>
</ul>

<p>But I do not know if this is a common practice or not.  Also I do not know if it is suitable for teaching.  The problem is that we sometimes want to define Ω() by liminf instead (as you did in the first definition).  For example, when we say “The probability of error of this randomized algorithm is 2<sup>−Ω(<i>n</i>)</sup>,” we do not mean that the error probability is exponentially small merely for <em>infinitely many</em> <i>n</i>!</p>

CC BY-SA 3.0
2011-07-28T16:34:39.570Z
@Tsuyoshi I like slimton's definition of $\Omega$ since it is symmetric with $O$ ($f=\Omega(g)$ iff $g=O(f)$) and it's easier to remember and apply: I find "for infinitely many values of" slightly confusing. Also a technical issue with your definition is the lack of transitivity, though I am not sure how critical that is.
Srivatsan Narayanan
CC BY-SA 3.0
2011-07-28T17:07:32.537Z
@Srivatsan: (1) Which definition lacks transitivity?  (2) I think that I clarified enough why I prefer the limsup definition to describe the complexity of an algorithm.  Whether you agree or not is up to you.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-28T17:18:00.500Z
Your definition lacks transitivity. You're right, I wanted to point out some merits (arguably not completely objective) of slimton's definition. But this site isn't the right place, sorry :-)
Srivatsan Narayanan
CC BY-SA 3.0
2011-07-28T17:33:05.277Z
In case anyone is wondering what an example of lack of transitivity @Srivatsan is talking about is: let f(n)=1, and let g(n) be 1 for n odd and n for n even.  Then under the limsup definition, f(n)=Ω(g(n)), g(n)=Ω(n), but f(n) is not Ω(n).
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-28T17:36:41.203Z
Tsuyoshi's example also works for $\Theta$. Just note that $f(n) = O(g(n))$ and $g(n) = O(n)$. Therefore, $f(n) = \Theta(g(n))$ and $g(n) = \Theta(n)$.
Srivatsan Narayanan
CC BY-SA 3.0
2011-09-29T21:58:53.067Z
@HeinrichApfelmus If memory serves, expected time of both Quicksort and Mergesort have oscillating components in $o(n)$ (random permutation model). For Mergesort at least, this is intuitive: splitting the list in equal parts works great for lengths of powers of two, but worse for those in between.
Raphael
CC BY-SA 2.5
2010-09-28T22:49:56.123Z
I also use the limsup definitions, but for students who haven't seen limsup (almost all of them) I have to expand into explicit quantifiers anyway.
Jeffε
CC BY-SA 2.5
2010-09-29T02:02:39.417Z
@JeffE: I agree that most students have not seen limsup, so if we use the limsup definitions, we have to use quantifiers instead in class.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T08:57:24.097Z
The problem with the quantifier versions is that they are difficult to remember and visualize. I prefer $limsup$ because it can be described as "highest limit point". A possible explanation is: "It is like $lim$, except that $lim$ only works when the sequence converges. If the sequence does not converge, for instance because the algorithm oscillates between very fast for some $n$ and slow for other $n$, then we take the highest limit point."
Heinrich Apfelmus
CC BY-SA 2.5
2010-09-29T08:59:44.927Z
Actually, are there any natural examples for algorithms where the running time does oscillate?
Heinrich Apfelmus
CC BY-SA 2.5
2010-09-29T11:37:43.820Z
@JeffE: I have just realized that I do not always use the limsup definition myself, and added the case where I used the liminf definition of Ω().
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T11:44:54.583Z
@Heinrich: I already mentioned the running time of an algorithm to find a perfect matching of a graph on n vertices, but does it count as a natural example?  I added another example where the running time does not oscillate but f(n)/g(n) oscillates.  The example speaks about space complexity, but the time complexity of the same example has the same property.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-30T09:03:17.407Z
Your new example is great, I like it!
Heinrich Apfelmus
CC BY-SA 2.5
2010-09-27T15:36:06.620Z
2010-09-29T11:14:54.090Z
2010-09-29T11:14:54.090Z
Tsuyoshi Ito
<p>Using limits is a bit confusing since (1) its a more complicated notion (2) it doesn't capture f=O(g) nicely (as we can see in the discussion above).  I usually talk about functions from the Natural (strictly positive) numbers to the Natural numbers  (which suffices for running times), skip the little-o stuff, and then the definition is concise and appropriate for 1st year undergrads:</p>

<p>Dfn: f=O(g) if for some C for all n we have that f(n)&lt;=C*g(n)</p>

CC BY-SA 3.0
2011-07-28T16:11:47.360Z
@Warren Victor Shoup in his book on [Computational Number Theory](http://shoup.net/ntb/ntb-v2.pdf) uses the notation $len(a)$ instead of $\log a$ in running time analysis, which I found neat.
Srivatsan Narayanan
CC BY-SA 3.0
2011-07-28T16:12:43.443Z
@Warren (continued) This is how he explains it: "In expressing the running times of algorithms in terms of an input $a$, we generally prefer to write $len(a)$ rather than $\log a$. One reason is esthetic: writing $len(a)$ stresses the fact that the running time is a function of the bit length of $a$. Another reason is technical: for big-$O$ estimates involving functions on an arbitrary domain, the appropriate inequalities should hold throughout the domain, and for this reason, it is very inconvenient to use functions, like $\log$, which vanish
or are undeﬁned on some input."
Srivatsan Narayanan
CC BY-SA 2.5
2010-09-29T13:21:13.350Z
First I did not like this definition because stating “all n” obscures the important fact that the O() notation only cares about the behavior of the functions for large n.  However, no matter which definition we choose, I guess that we should explain this fact together with the definition.  Thinking that way, stating this simple definition seems quite good.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T17:55:18.027Z
While this captures the essence, I dislike that if $f(n) = n$ for all $n$, $g(n) = 0$ for all $n$ up to $N_0$, and $g(n) = f(n)+1$ otherwise, then $f=O(g)$ but this definition fails to capture this relationship.  So one has to add some handwaving about functions that are well-behaved in some sense.
András Salamon
CC BY-SA 2.5
2010-09-29T19:20:13.313Z
The point of talking about functions whose range is the Natural numbers (not including 0) is exactly not to fall into problems with g(n)=0.
Noam
CC BY-SA 2.5
2010-09-29T20:15:09.600Z
What do you give as the runtime for quicksort? The classic O(n log n) is out since it's zero at n-1. Do you use n nlog (2n) or something like that?
Warren Schudy
CC BY-SA 2.5
2010-09-29T20:17:41.360Z
Note that the introductory algorithms text by DasGupta and Vazirani uses this definition.
Warren Schudy
CC BY-SA 2.5
2010-09-29T12:02:02.583Z
2010-09-29T12:02:02.583Z
Noam
<p>When I took basic courses, we were given the $\exists c,n_0 \dots$ thing as definition and the other stuff as theorem.</p>

<p>I think the first one is more natural for many people that think discrete rather than continuous, that is most computer scientists (in my experience). It also fits the way we usually talk about those things better: "There is a polynomial function of degree 3 that is an upper bound for this $f$ up to a constant factor."</p>

<p><strong>Edit</strong>: You can get even closer to this way of speaking if you use this definition:
$f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$
(Note that $d=f(n_0)$ connects this definition with the one usually given) </p>

<p>The limit stuff is pretty useful for calculating complexity classes, that is with pen and paper.</p>

<p>In any case, I think it is very useful for students to learn that there is a wealth of (hopefully) equivalent definitions. They should be able to realize that and pick out differences in case of nonequivalent definitions.</p>

CC BY-SA 2.5
2010-09-28T18:43:25.453Z
2010-09-29T11:44:40.763Z
2010-09-29T11:44:40.763Z
Raphael
<p>Having studied these concepts only a few years ago, they were not the hardest ones to grasp for my class (as opposed to concepts like induction, or contra positives). Limits and limsups are only more "intuitive" for those familiar with calculus in my opinion. But students with such a math grounding will have set-theoretic background anyway, so that they can process discrete qualifiers. </p>

<p>Also, more importantly, remember that ultimately your students will go on (hopefully) to read other cs theory textbooks, and perhaps even research papers one day. As such, it is better for them to be comfortable with standard notation in the field, even if it was not ideally conceived initially.  There is no harm giving them alternate definitions as well, once they've assimilated the standard ones.</p>

CC BY-SA 3.0
2011-07-28T08:10:03.330Z
2011-07-28T08:10:03.330Z
Amir
<p>For an interesting take on the issue, look at Don Knuth's nicely written letter <a href="http://micromath.wordpress.com/2008/04/14/donald-knuth-calculus-via-o-notation/" rel="nofollow">"Calculus via O notation"</a>.  He advocates the reverse view that calculus should be taught via the 'A', 'O' and 'o' notations. </p>

<p>Note: He uses the "A" notation as a preliminary step in defining the standard "O" notation. A quantity $x$ is $A$ of $y$ (i.e., $x = A(y)$), if  $|x| \leq y$. In particular, it makes sense  to say $100$ is $A(200)$. </p>

CC BY-SA 3.0
2011-07-27T15:01:45.257Z
2011-07-28T16:42:36.507Z
2011-07-28T16:42:36.507Z
Srivatsan Narayanan
<ol>
<li><p>Tsuyoshi Ito's definitions don't look quite right. For little-omega and big-omega the definitions should use liminf, not limsup. The definition of big-theta needs both a lower-bound on liminf and an upper-bound on limsup.</p></li>
<li><p>One definition of f(n)=O(g(n)) is that there exists another function f'(n) >= f(n) such that lim f'(n)/g(n) &lt;  infinity.</p></li>
<li><p>Why are newbies allowed to post answers but not make comments?</p></li>
</ol>

CC BY-SA 2.5
2010-09-27T19:32:43.187Z
As for item 1, I mean limsup in all cases, and the reason is explained in the second paragraph of my answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-28T02:57:30.310Z
it's a spam blocking mechanism unfortunately.
Suresh Venkat
CC BY-SA 2.5
2010-09-28T02:57:46.080Z
Aso, you can use latex in your answers.
Suresh Venkat
CC BY-SA 2.5
2010-09-27T16:26:43.690Z
2010-09-27T16:26:43.690Z
Warren Schudy
<p><strong>First</strong>, I try to <strong>develop</strong> in students some <strong>intuition</strong>, before showing equations.</p>

<ul>
<li>"Merge-sort vs Insertion-Sort" is good starting point.</li>
</ul>

<p>Then, later... I try to show both ways. Students, that relies more on intuition prefer $$f = O(g) \mbox{ iff } (\exists c &gt; 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).$$
while those who relies more on math, equasions, algebra etc. , they prefer "$\lim_{n \rightarrow \infty}$" definitions.</p>

<p>Another aspect is that, it heavily depends on concrete studies' program. IMHO depending on previous subjects one of definitions will be more suitable - while IMHO still it is good idea to show both and accept both types of solutions.</p>

CC BY-SA 3.0
2011-09-08T08:25:34.850Z
2011-09-08T08:45:25.787Z
2011-09-08T08:45:25.787Z
Grzegorz Wierzowiecki
<p>When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).
$$
Perhaps we even give the whole list with all its quantifiers:</p>

<ol>
<li>$f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$</li>
<li>$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$</li>
<li>$f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$</li>
<li>$f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$</li>
<li>$f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$.</li>
</ol>

<p>However, since these definitions are not so easy to work with when it comes to proving even simple things such as $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$, most of us quickly move to introduce the "trick of the limit": </p>

<ol>
<li>$f = o(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $0$,</li>
<li>$f = O(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $+\infty$,</li>
<li>$f = \Theta(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is neither $0$ nor $+\infty$,</li>
<li>$f = \Omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $0$,</li>
<li>$f = \omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $+\infty$.</li>
</ol>

<p>My question is: </p>

<p>Would it be a big loss for teaching an undergraduate algorithms class to take the limit conditions as <em>the</em> definitions of $o$, $O$, $\Theta$, $\Omega$, and $\omega$? That's what we all end-up using anyway and it seems pretty clear to me that skipping the quantifier definitions makes everybody's life easier.</p>

<p>I would be interested to know if you have encountered some convincing natural case where the standard $c,n_0$-definitions are actually required, and if not, whether you have a convincing argument to keep the standard $c,n_0$-definitions upfront anyway.</p>

CC BY-SA 2.5
2011-01-20T08:03:37.190Z
Definition 1 in [Tao's review of probability](http://terrytao.wordpress.com/2010/01/01/254a-notes-0-a-review-of-probability-theory/) is kind of cute.
Radu GRIGore
CC BY-SA 2.5
2011-03-20T14:29:00.820Z
See also related discussion http://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds which deals with the case where there is no limit, such as oscillating functions.
András Salamon
CC BY-SA 3.0
2011-07-28T11:28:52.690Z
In my CS course, we were taught the first set, and in my math course, when we were taught the little-o notation, we were taught in the second style. I guess it boils down to what are the primitives known to the students.
Ohad Kammar
CC BY-SA 3.0
2011-07-28T18:05:12.180Z
Shouldn't you replace the symbol $=$ by $\in$ in each definition and property? I found the use of $=$ very disturbing as a student.
J.y B.y
CC BY-SA 2.5
2010-09-27T14:27:43.377Z
The tag should really be "teaching" but I couldn't find any related tag and I am not allowed to create new tags.
slimton
CC BY-SA 2.5
2010-09-27T14:44:20.387Z
Interesting question/thought; I like it!
Daniel Apon
CC BY-SA 2.5
2010-09-27T14:48:52.833Z
This basically absorbs the quantifiers into the epsilon-delta definition of limits. My only concern would be that many CS students haven't taken analysis and so their understanding of limits is mostly mechanical. For enabling them to quickly calculate, though, it's a no-brainer.
Per Vognsen
CC BY-SA 2.5
2010-09-27T14:49:44.667Z
Note that your two definitions of O() are not equivalent (the same caveat applies to Θ() and Ω()).  Consider the case where f(n)=2n for even n and f(n)=1 for odd n.  Is f(n)=O(n)?  I prefer to use limsup instead of lim so that I can say f(n)=Θ(n) in this case (although neither of your definitions allows this).  But this may be my personal preference (and even a nonstandard practice), and I have never taught a class.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T15:09:35.470Z
@Tsuyoshi: I thought the point of the "limit trick" was that it was a sufficient but not necessary condition for $O()$.  (For $o()$ it is also necessary.)  The oscillating function counterexample does not have a limit.
András Salamon
CC BY-SA 2.5
2010-09-27T15:14:14.917Z
@András: I overlooked that the second group of definitions stated “if,” not “if and only if.”  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T17:22:02.653Z
Could $n_0$ be dropped in the first set of definitions? (Assuming that f(n) and g(n) are defined for all $n\ge 0$.)
Emil
CC BY-SA 2.5
2010-09-27T20:36:54.043Z
@Emil: I think that some of them can be dropped, but they cannot be dropped in the definitions of the small o() and small ω().
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T23:49:13.470Z
@Tsuyoshi: Yes you're right, it is needed for them, but not for the others from what I can tell.
Emil
<ds.algorithms><soft-question><teaching>
Which definition of asymptotic growth-rate should we teach?
slimton
# Which definition of asymptotic growth-rate should we teach?

(Asked by: username_0 on 2010-09-27)

When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \leq c \cdot g(n)).
$$
Perhaps we even give the whole list with all its quantifiers:

1. $f = o(g) \mbox{ iff } (\forall c > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \leq c \cdot g(n))$
2. $f = O(g) \mbox{ iff } (\exists c > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \leq c \cdot g(n))$
3. $f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
4. $f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \geq d \cdot g(n))$
5. $f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \geq d \cdot g(n))$.

However, since these definitions are not so easy to work with when it comes to proving even simple things such as $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$, most of us quickly move to introduce the "trick of the limit":

1. $f = o(g)$ if $\lim\_{n \rightarrow \infty} f(n)/g(n)$ exists and is $0$,
2. $f = O(g)$ if $\lim\_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $+\infty$,
3. $f = \Theta(g)$ if $\lim\_{n \rightarrow \infty} f(n)/g(n)$ exists and is neither $0$ nor $+\infty$,
4. $f = \Omega(g)$ if $\lim\_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $0$,
5. $f = \omega(g)$ if $\lim\_{n \rightarrow \infty} f(n)/g(n)$ exists and is $+\infty$.

My question is:

Would it be a big loss for teaching an undergraduate algorithms class to take the limit conditions as *the* definitions of $o$, $O$, $\Theta$, $\Omega$, and $\omega$? That's what we all end-up using anyway and it seems pretty clear to me that skipping the quantifier definitions makes everybody's life easier.

I would be interested to know if you have encountered some convincing natural case where the standard $c,n\_0$-definitions are actually required, and if not, whether you have a convincing argument to keep the standard $c,n\_0$-definitions upfront anyway.

**Tags:** ds.algorithms, soft-question, teaching

> **Comments:**
> **username_0**: The tag should really be "teaching" but I couldn't find any related tag and I am not allowed to create new tags.  
> **username_5**: Interesting question/thought; I like it!  
> **username_6**: This basically absorbs the quantifiers into the epsilon-delta definition of limits. My only concern would be that many CS students haven't taken analysis and so their understanding of limits is mostly mechanical. For enabling them to quickly calculate, though, it's a no-brainer.  
> **username_7**: Note that your two definitions of O() are not equivalent (the same caveat applies to Θ() and Ω()).  Consider the case where f(n)=2n for even n and f(n)=1 for odd n.  Is f(n)=O(n)?  I prefer to use limsup instead of lim so that I can say f(n)=Θ(n) in this case (although neither of your definitions allows this).  But this may be my personal preference (and even a nonstandard practice), and I have never taught a class.  
> **username_2**: @Tsuyoshi: I thought the point of the "limit trick" was that it was a sufficient but not necessary condition for $O()$.  (For $o()$ it is also necessary.)  The oscillating function counterexample does not have a limit.  
> **username_7**: @András: I overlooked that the second group of definitions stated “if,” not “if and only if.”  Thanks!  
> **username_8**: Could $n_0$ be dropped in the first set of definitions? (Assuming that f(n) and g(n) are defined for all $n\ge 0$.)  
> **username_7**: @username_8: I think that some of them can be dropped, but they cannot be dropped in the definitions of the small o() and small ω().  
> **username_8**: @Tsuyoshi: Yes you're right, it is needed for them, but not for the others from what I can tell.  
> **username_1**: Definition 1 in [Tao's review of probability](http://terrytao.wordpress.com/2010/01/01/254a-notes-0-a-review-of-probability-theory/) is kind of cute.  
> **username_2**: See also related discussion http://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds which deals with the case where there is no limit, such as oscillating functions.  
> **username_3**: In my CS course, we were taught the first set, and in my math course, when we were taught the little-o notation, we were taught in the second style. I guess it boils down to what are the primitives known to the students.  
> **username_4**: Shouldn't you replace the symbol $=$ by $\in$ in each definition and property? I found the use of $=$ very disturbing as a student.  

---

## 8 answers

### Answer by username_9 on 2010-09-27. Score: 13

I prefer teaching the original definition with quantifiers.

IMO, humans generally have trouble in understanding formulas and definitions with more than two alternation of quantifiers directly. Introducing new quantifiers can clarify what the definition means. Here, the last two quantifiers just mean "for all sufficiently large n", introducing this kind of quantification can help.

The pictures I draw for explaining these concepts match better with the quantifier versions.

I think the limit simplification is useful for engineering student who are only interested in computing the growth rate, but won't be as useful for computer science students. In fact, using this simplification can cause more harm than good.

This idea is similar to suggestion that we use the rules for computing derivatives (of polynomials, exponentiation, ..., chain rule, ...) in place of the epsilon-delta definition of it, which IMHO is not a good idea.

> **Comments:**
> **username_9**: The eventual domination notion is also helpful: $f(x) \ll g(x)$ iff $\esits m \forall n>m f(n) < g(n)$. Now $f \in O(g)$ iff there is $c>0$ s.t. $f(x) \ll c g(x)$.  

---

### Answer by username_7 on 2010-09-27. Score: 9

*Edit: Major revision in revision 3.*

Since I have never taught a class, I do not think that I can claim anything convincingly about what we should teach. Nevertheless, here are what I thought about it.

There are natural examples where the “limit trick” as is written cannot be applied. For example, suppose you implement a “variable-length vector” (like vector in C++) by using a fixed-length array with size doubling (that is, every time you are about to exceed the size of the array, you reallocate the array twice as large as now and copy all the elements). The size *S*(*n*) of the array when we store *n* elements in the vector is the smallest power of 2 greater than or equal to *n*. We want to say that *S*(*n*)=O(*n*), but using the “limit trick” as is written as definition would not allow us to do so because *S*(*n*)/*n* oscillates densely in the range [1,2). The same applies to Ω() and Θ().

As a somewhat separate matter, when we use these notations to describe the complexity of an algorithm, I think that your definition of Ω() is sometimes inconvenient (although I guess that that definition is common). It is more convenient to define that *f*(*n*)=Ω(*g*(*n*)) if and only if limsup *f*(*n*)/*g*(*n*) > 0. This is because some problems are trivial for infinitely many values of n (such as the perfect maching problem on a graph with an odd number *n* of vertices). The same applies to Θ() and ω().

Therefore, I personally find that the following definitions the most convenient to use to describe the complexity of an algorithm: for functions *f*, *g*: ℕ → ℝ>0,

* *f*(*n*)=o(*g*(*n*)) if and only if limsup *f*(*n*)/*g*(*n*) = 0. (This is equivalent to lim *f*(*n*)/*g*(*n*) = 0.)
* *f*(*n*)=O(*g*(*n*)) if and only if limsup *f*(*n*)/*g*(*n*) < ∞.
* *f*(*n*)=Θ(*g*(*n*)) if and only if 0 < limsup *f*(*n*)/*g*(*n*) < ∞.
* *f*(*n*)=Ω(*g*(*n*)) if and only if limsup *f*(*n*)/*g*(*n*) > 0. (This is equivalent to that *f*(*n*) is not o(*g*(*n*)).)
* *f*(*n*)=ω(*g*(*n*)) if and only if limsup *f*(*n*)/*g*(*n*) = ∞. (This is equivalent to that *f*(*n*) is not O(*g*(*n*)).)

or equivalently,

* *f*(*n*)=o(*g*(*n*)) if and only if for every *c*>0, for sufficiently large *n*, *f*(*n*) ≤ *c*⋅*g*(*n*).
* *f*(*n*)=O(*g*(*n*)) if and only if for some *c*>0, for sufficiently large *n*, *f*(*n*) ≤ *c*⋅*g*(*n*).
* *f*(*n*)=Θ(*g*(*n*)) if and only if *f*(*n*)=O(*g*(*n*)) and *f*(*n*)=Ω(*g*(*n*)).
* *f*(*n*)=Ω(*g*(*n*)) if and only if for some *d*>0, for infinitely many *n*, *f*(*n*) ≥ *d*⋅*g*(*n*).
* *f*(*n*)=ω(*g*(*n*)) if and only if for every *d*>0, for infinitely many *n*, *f*(*n*) ≥ *d*⋅*g*(*n*).

But I do not know if this is a common practice or not. Also I do not know if it is suitable for teaching. The problem is that we sometimes want to define Ω() by liminf instead (as you did in the first definition). For example, when we say “The probability of error of this randomized algorithm is 2−Ω(*n*),” we do not mean that the error probability is exponentially small merely for *infinitely many* *n*!

> **Comments:**
> **username_12**: I also use the limsup definitions, but for students who haven't seen limsup (almost all of them) I have to expand into explicit quantifiers anyway.  
> **username_7**: @JeffE: I agree that most students have not seen limsup, so if we use the limsup definitions, we have to use quantifiers instead in class.  
> **username_13**: The problem with the quantifier versions is that they are difficult to remember and visualize. I prefer $limsup$ because it can be described as "highest limit point". A possible explanation is: "It is like $lim$, except that $lim$ only works when the sequence converges. If the sequence does not converge, for instance because the algorithm oscillates between very fast for some $n$ and slow for other $n$, then we take the highest limit point."  
> **username_13**: Actually, are there any natural examples for algorithms where the running time does oscillate?  
> **username_7**: @JeffE: I have just realized that I do not always use the limsup definition myself, and added the case where I used the liminf definition of Ω().  
> **username_7**: @Heinrich: I already mentioned the running time of an algorithm to find a perfect matching of a graph on n vertices, but does it count as a natural example?  I added another example where the running time does not oscillate but f(n)/g(n) oscillates.  The example speaks about space complexity, but the time complexity of the same example has the same property.  
> **username_13**: Your new example is great, I like it!  
> **username_10**: @Tsuyoshi I like username_0's definition of $\Omega$ since it is symmetric with $O$ ($f=\Omega(g)$ iff $g=O(f)$) and it's easier to remember and apply: I find "for infinitely many values of" slightly confusing. Also a technical issue with your definition is the lack of transitivity, though I am not sure how critical that is.  
> **username_7**: @Srivatsan: (1) Which definition lacks transitivity?  (2) I think that I clarified enough why I prefer the limsup definition to describe the complexity of an algorithm.  Whether you agree or not is up to you.  
> **username_10**: Your definition lacks transitivity. You're right, I wanted to point out some merits (arguably not completely objective) of username_0's definition. But this site isn't the right place, sorry :-)  
> **username_7**: In case anyone is wondering what an example of lack of transitivity @Srivatsan is talking about is: let f(n)=1, and let g(n) be 1 for n odd and n for n even.  Then under the limsup definition, f(n)=Ω(g(n)), g(n)=Ω(n), but f(n) is not Ω(n).  
> **username_10**: Tsuyoshi's example also works for $\Theta$. Just note that $f(n) = O(g(n))$ and $g(n) = O(n)$. Therefore, $f(n) = \Theta(g(n))$ and $g(n) = \Theta(n)$.  
> **username_11**: @HeinrichApfelmus If memory serves, expected time of both Quicksort and Mergesort have oscillating components in $o(n)$ (random permutation model). For Mergesort at least, this is intuitive: splitting the list in equal parts works great for lengths of powers of two, but worse for those in between.  

---

### Answer by username_14 on 2010-09-29. Score: 8

Using limits is a bit confusing since (1) its a more complicated notion (2) it doesn't capture f=O(g) nicely (as we can see in the discussion above). I usually talk about functions from the Natural (strictly positive) numbers to the Natural numbers (which suffices for running times), skip the little-o stuff, and then the definition is concise and appropriate for 1st year undergrads:

Dfn: f=O(g) if for some C for all n we have that f(n)<=C\*g(n)

> **Comments:**
> **username_7**: First I did not like this definition because stating “all n” obscures the important fact that the O() notation only cares about the behavior of the functions for large n.  However, no matter which definition we choose, I guess that we should explain this fact together with the definition.  Thinking that way, stating this simple definition seems quite good.  
> **username_2**: While this captures the essence, I dislike that if $f(n) = n$ for all $n$, $g(n) = 0$ for all $n$ up to $N_0$, and $g(n) = f(n)+1$ otherwise, then $f=O(g)$ but this definition fails to capture this relationship.  So one has to add some handwaving about functions that are well-behaved in some sense.  
> **username_14**: The point of talking about functions whose range is the Natural numbers (not including 0) is exactly not to fall into problems with g(n)=0.  
> **username_15**: What do you give as the runtime for quicksort? The classic O(n log n) is out since it's zero at n-1. Do you use n nlog (2n) or something like that?  
> **username_15**: Note that the introductory algorithms text by DasGupta and Vazirani uses this definition.  
> **username_10**: @Warren Victor Shoup in his book on [Computational Number Theory](http://shoup.net/ntb/ntb-v2.pdf) uses the notation $len(a)$ instead of $\log a$ in running time analysis, which I found neat.  
> **username_10**: @Warren (continued) This is how he explains it: "In expressing the running times of algorithms in terms of an input $a$, we generally prefer to write $len(a)$ rather than $\log a$. One reason is esthetic: writing $len(a)$ stresses the fact that the running time is a function of the bit length of $a$. Another reason is technical: for big-$O$ estimates involving functions on an arbitrary domain, the appropriate inequalities should hold throughout the domain, and for this reason, it is very inconvenient to use functions, like $\log$, which vanish or are undeﬁned on some input."  

---

### Answer by username_11 on 2010-09-28. Score: 5

When I took basic courses, we were given the $\exists c,n\_0 \dots$ thing as definition and the other stuff as theorem.

I think the first one is more natural for many people that think discrete rather than continuous, that is most computer scientists (in my experience). It also fits the way we usually talk about those things better: "There is a polynomial function of degree 3 that is an upper bound for this $f$ up to a constant factor."

**Edit**: You can get even closer to this way of speaking if you use this definition:
$f \in \mathcal{O}(g) :\Leftrightarrow \exists c,d > 0 \forall n \geq 0 : f(n) \leq c\cdot g(n) + d$
(Note that $d=f(n\_0)$ connects this definition with the one usually given)

The limit stuff is pretty useful for calculating complexity classes, that is with pen and paper.

In any case, I think it is very useful for students to learn that there is a wealth of (hopefully) equivalent definitions. They should be able to realize that and pick out differences in case of nonequivalent definitions.


---

### Answer by username_16 on 2011-07-28. Score: 4

Having studied these concepts only a few years ago, they were not the hardest ones to grasp for my class (as opposed to concepts like induction, or contra positives). Limits and limsups are only more "intuitive" for those familiar with calculus in my opinion. But students with such a math grounding will have set-theoretic background anyway, so that they can process discrete qualifiers.

Also, more importantly, remember that ultimately your students will go on (hopefully) to read other cs theory textbooks, and perhaps even research papers one day. As such, it is better for them to be comfortable with standard notation in the field, even if it was not ideally conceived initially. There is no harm giving them alternate definitions as well, once they've assimilated the standard ones.


---

### Answer by username_10 on 2011-07-27. Score: 3

For an interesting take on the issue, look at Don Knuth's nicely written letter ["Calculus via O notation"](http://micromath.wordpress.com/2008/04/14/donald-knuth-calculus-via-o-notation/). He advocates the reverse view that calculus should be taught via the 'A', 'O' and 'o' notations.

Note: He uses the "A" notation as a preliminary step in defining the standard "O" notation. A quantity $x$ is $A$ of $y$ (i.e., $x = A(y)$), if $|x| \leq y$. In particular, it makes sense to say $100$ is $A(200)$.


---

### Answer by username_15 on 2010-09-27. Score: 1

1. username_7's definitions don't look quite right. For little-omega and big-omega the definitions should use liminf, not limsup. The definition of big-theta needs both a lower-bound on liminf and an upper-bound on limsup.
2. One definition of f(n)=O(g(n)) is that there exists another function f'(n) >= f(n) such that lim f'(n)/g(n) < infinity.
3. Why are newbies allowed to post answers but not make comments?

> **Comments:**
> **username_7**: As for item 1, I mean limsup in all cases, and the reason is explained in the second paragraph of my answer.  
> **username_17**: it's a spam blocking mechanism unfortunately.  
> **username_17**: Aso, you can use latex in your answers.  

---

### Answer by username_18 on 2011-09-08. Score: 1

**First**, I try to **develop** in students some **intuition**, before showing equations.

* "Merge-sort vs Insertion-Sort" is good starting point.

Then, later... I try to show both ways. Students, that relies more on intuition prefer $$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n\_0 \geq 0)(\forall n \geq n\_0)(f(n) \leq c \cdot g(n)).$$
while those who relies more on math, equasions, algebra etc. , they prefer "$\lim\_{n \rightarrow \infty}$" definitions.

Another aspect is that, it heavily depends on concrete studies' program. IMHO depending on previous subjects one of definitions will be more suitable - while IMHO still it is good idea to show both and accept both types of solutions.


---

