Haciendo el análisis de la complejidad de los algoritmos, se limita a menudo a su complejidad asintótica. Una función de $g: \mathbb N \to \mathbb R_+$ es asintóticamente delimitada por $f: \mathbb N \to \mathbb R_+$ si hay constantes $c \in \mathbb R_+, N \in \mathbb N$ tal que para cada una de las $n \geq N$, $$ g(n) \leq c\cdot f(n). $$ El conjunto de todos los $g$ se conoce como $\mathcal O(f)$. Dejando $g \preceq f$ si $\mathcal O(g) \subseteq \mathcal O(f)$, obtenemos un reservas en el conjunto de las funciones de $\mathbb N \to \mathbb R_+$.
Ejemplos de funciones que normalmente se presentan como las complejidades de los algoritmos son: $$\etiqueta{*} \log(\log(n)), \log(n),\log(n)^2, \sqrt{n}, n, n\log(n),n\sqrt{n},n^3, 2^n, 3^n, 2^{2^n}. $$ Curiosamente, estas funciones son todos los linealmente ordenado por $\preceq$. Se nota que no es difícil encontrar funciones que no linealmente ordenado por $\preceq$, como $|\sin(n)|$$|\cos(n)|$, y con un poco de tocar el violín no sería demasiado duro para hacer ejemplos de estrictamente creciente (o incluso convexo) funciones que no son linealmente ordenado por $\preceq$. Sin embargo, todos estos ejemplos parecen artificiales, y, en particular, me sorprendería si es que alguna vez llegó hasta como las complejidades de los algoritmos.
Podemos explícitamente dar una buena clase de funciones que incluye, al menos, todas las funciones que figuran en (*), y para los que $\preceq$ es lineal hacer el pedido? Es esta clase también cerrado, en virtud de algunas operaciones, como la multiplicación, la exponenciación por una constante, o tomando logaritmos? Y, tal vez, se podría incluso justificar por qué el algoritmo es probable que tenga una complejidad en esta clase?
