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:
- $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))$
- $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))$
- $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))$
- $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))$
- $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":
- $f = o(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $0$,
- $f = O(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $+\infty$,
- $f = \Theta(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is neither $0$ nor $+\infty$,
- $f = \Omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $0$,
- $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.