6
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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). $\endgroup$
    – Raphael
    Commented Mar 15, 2013 at 7:38
  • $\begingroup$ Furthermore, make sure to fix the base set of functions. For some choices, different definitions are equivalent, but for others, they are not. $\endgroup$
    – Raphael
    Commented Mar 15, 2013 at 10:03
  • $\begingroup$ 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. $\endgroup$
    – Patrick87
    Commented Mar 15, 2013 at 15:51

2 Answers 2

Reset to default
7
$\begingroup$

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$.
Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.