1

Algorithm Design: Foundations, Analysis, and Internet Examples by Goodrich and Tamassia (Wiley, 2002) defines little-o as follows:

$o(g(n)) = \{ f(n) : \forall c > 0,\ \exists n_0 > 0\ \text{such that } \forall n \geq n_0,\ 0 \leq f(n) \leq cg(n) \}$.

This definition differs slightly by strictness in the last inequality from that of Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein (MIT, 2009) which defines as:

$o(g(n)) = \{ f(n) : \forall c > 0,\ \exists n_0 > 0\ \text{such that } \forall n \geq n_0,\ 0 \leq f(n) < cg(n) \}$.

The latter definition is what I primarily see in other sources, too. Are these equivalent due to the choice of any constant c? If not, which is standard? (I assume it is the CLRS one.)

Heather Guarnera
  • 538
  • 1
    The CLRS has $o(0)=\emptyset$, for one thing, whereas GT has $o(0)={\text{sequences that are eventually }0}$. –  Aug 22 '19 at 17:42
  • Also, CRLS has $o(g)=\emptyset$ for all $g$ which are frequently $0$. –  Aug 22 '19 at 17:44
  • Personally, I like better $o(g)={f,:, \forall c>0,\exists m,\ \forall n>m,\ \lvert f(n)\rvert\le c\lvert g(n)\rvert}$. –  Aug 22 '19 at 17:46
  • 1
    @Gae.S. Do you mean to write $n \geq n_0$ in both definitions? – kccu Aug 22 '19 at 17:48
  • @kccu Yes, I corrected above. – Heather Guarnera Aug 22 '19 at 17:49
  • @Gae.S. Thanks, those are good examples. Is this difference common among varying little-o definitions or is GT an outlier? – Heather Guarnera Aug 22 '19 at 17:50
  • 1
    @Agrajag I don't know. My opinion is that CRLS might have had the one by GT in mind and that they overlooked the pathologies of the more general situation because they were concerned just with strictly increasing functions. –  Aug 22 '19 at 19:14

1 Answers1

2

Neither one is standard. $$o(g)=\{f: \forall c>0\,\exists n_0\,\forall n>n_0\,(|f(n)|\le c|g(n)|)\}.$$

DanielWainfleet
  • 57,985
  • It is also common to write that a function is $equal$ to $o(g)$ which means that it belongs to the $set$ $o(g)$. E.g. $n^2+3n=n^2(1+o(1)).$ – DanielWainfleet Aug 23 '19 at 20:51