# Landau Notation, Definitions: Limits vs. Corman's

When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.:

$$o(g(n))=\{ f(n): \forall c>0:\exists n_0>0:\; 0\leq f(n) < cg(n): \; \forall n\geq n_0 \}$$

and some texts use limit based definitions such as:

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0\Rightarrow f(n)\in o(g(n))$$

Is there any inherent advantage to one definition or the other? Or is it more a matter of the author's personal preference?

• The second is not even a definition, as you can see by $\implies$, i.e. the notable absence of $\Longleftarrow$. Nevertheless, it can be extended to a definition. As an exercise, prove that it is equivalent to the first one (which is not always the case with Landau definitions). – Raphael Mar 15 '13 at 7:38
• Furthermore, make sure to fix the base set of functions. For some choices, different definitions are equivalent, but for others, they are not. – Raphael Mar 15 '13 at 10:03
• If your question is really Is there any inherent advantage to one definition or the other? Or is it more a matter of the author's personal preference?, the answer is that, yes, it is up to the author's preference which definition s/he uses. That seems almost tautological. – Patrick87 Mar 15 '13 at 15:51

## 2 Answers

To expand on Raphael's answer, both definitions are equivalent. The second definition is Landau-style (i.e. number theory style), while the first definition is computer science style.

The Landau-style definition is clearly more succinct and I personally prefer it. There are two reasons to state the definition in the computer science style:

1. Textbook writers don't want to assume that their readers know calculus.
2. The Landau-style definition for $f = \Theta(g)$ is more awkward: $\lim\inf f/g > 0$, $\lim\sup f/g < \infty$.

The second definition is often handy when comparing functions w.r.t asymptotic growth since evaluating one limit is (usually) easier than showing something for all $c$.