El mal uso de la notación de la función $f(n)$

Question

Recientemente he leído en un libro sobre la teoría de la complejidad computacional: $$ O(f(n)) = \{g:\mathbb N \to\mathbb R \cup \{0\} : \exists \xi > 0,n_0\in \mathbb N\;\: g(n) \leq \xi \cdot f(n) \;\: \forall n \geq n_0 \} $$ Pero creo que debería ser $O(f)$ desde la notación $f(n)$ denota la imagen de $n$ bajo $f$. Es esto correcto? Gracias de antemano.

Edit: ¿Cuál es su opinión acerca de la $O(\log n)$? Debemos considerar la $\log n: \mathbb N \to\mathbb R^+\cup\{0\}, n \mapsto \log(n)$?

Answer 1

Usted está en lo correcto. Debería ser $O(f),$ o de lo $(Om \in \mathbb{N})(f(m)),$, pero ciertamente no $O(f(m))$. En realidad, la mejor solución sería escribir: Vamos a $\mathbb{O}(f(m))$ ser la abreviatura de $(Om \in \mathbb{N})(f(m)).$, por Lo que, cada vez que usted vea el autor abusando de la notación por escrito $O(f(m))$, sólo piensa en $\mathbb{O}(f(m))$ y vas a estar bien.