2

What's the notation for ranking functions in increasing asymptotic order? I saw a notation with $\prec$ earlier, but now I can't find it. Would the following notation be correct?

$$\mathcal{O}(n)\prec \mathcal{O}(n\log n)$$

hardmath
  • 37,015
Steve
  • 179
  • 7
    Incidentally, the "correct" interpretation of big-oh is that they are sets of functions (and that $f=O(g)$ better be written $f\in O(g)$). In that light, $\subset$ is the natural notation – Hagen von Eitzen Mar 02 '17 at 07:12
  • 3
    Sometimes people use little-oh to represent the case where $f$ is $O(g)$ but $f$ is not $\Theta(g)$. – Michael Burr Mar 02 '17 at 13:28
  • Michael Burr, you are right for monotonic functions or some other classes, but not in general. E. g. $f(x) = x (1 + \sin^2 x) = O(x)$, but $f$ is neither in $\Theta(x)$, nor in $o(x)$. – Smylic Mar 02 '17 at 18:15

1 Answers1

2

Donald Knuth, Oren Patashnik, and Ronald Graham in their textbook "Concrete Mathematics" (chapter 9) really use this notation for functions (not for sets of functions): $$f(n) \prec g(n) \iff \lim_{n \to \infty}\frac{f(n)}{g(n)} = 0. \tag{9.3}$$ This notation was introduced by Paul du Bois-Reymond in 1871. Also, as noted in the comments, you can write the same relation as $f(n) = o(g(n))$ meaning that $f(n) \in o(g(n))$. However $f(n) \prec g(n) \iff g(n) \succ f(n)$, but relation $\color{red}{o(g(n)) = f(n)}$ is invalid. Swapping $f$ and $g$ leads to $g(n) = \omega(f(n))$ or $g(n) \in \omega(f(n))$.

Smylic
  • 6,715