principleMinor
Landau Notation, Definitions: Limits vs. Corman's
Viewed 0 times
limitsnotationlandaucormandefinitions
Problem
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?
$$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?
Solution
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:
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:
- Textbook writers don't want to assume that their readers know calculus.
- The Landau-style definition for $f = \Theta(g)$ is more awkward: $\lim\inf f/g > 0$, $\lim\sup f/g
Context
StackExchange Computer Science Q#10531, answer score: 7
Revisions (0)
No revisions yet.