HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

Landau Notation, Definitions: Limits vs. Corman's

Submitted by: @import:stackexchange-cs··
0
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?

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:

  • 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.