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?

$\endgroup$
  • 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 Mar 15 '13 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 Mar 15 '13 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 Mar 15 '13 at 15:51
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$.
$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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