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.
Which definition of asymptotic growth-rate should we teach?
ds.algorithms;soft question;teaching