¿Existe siempre una complejidad de Big Oh estrictamente entre cualquiera de los otros dos?

Estoy aprendiendo sobre el análisis asintótico, y he visto algunas complejidades de aspecto exótico que viven entre otras comunes. Por ejemplo, "log log n" está estrictamente entre 1 y log n. Me hace preguntarme si uno siempre puede encontrar complejidades entre otros dos.

Específicamente, para cualquier función f y g con O (f) ⊂ O (g) ¿existe siempre una h tal que O (f) ⊂ O (h) ⊂ O (g)?

Esto no es tarea ni nada. Solo tengo curiosidad si alguien lo sabe.

Sí: tome una función en el medio, para una definición adecuada de medio. Tienes una amplia elección.

Si $O(f) \subset O(g)$ (donde la inclusión es estricta), entonces $g \in O(g) \setminus O(f)$ (porque si $g \in O(f)$ y $f \in O(g)$ entonces $\Theta(f) = \Theta(g)$) Toma la media geométrica: deja$h = \sqrt{f \cdot g}$ (Como estamos hablando de complejidad aquí, supongo que las funciones son positivas).

Entonces $f \in O(h)$ y $h \in O(g)$ (si esto no es inmediatamente obvio, demuéstralo usando la definición de $O$), es decir $O(f) \subseteq O(h) \subseteq O(g)$. Si$O(f) = O(h)$ entonces $g = f \in O(f)$, que no es el caso ya que asumimos $g \notin O(f)$. Queda por demostrar que$O(h) \ne O(g)$y tendremos $O(f) \subset O(h) \subset (g)$.

Si $O(h) = O(g)$ entonces $g \in O(h)$es decir, existe $A$ y $C \gt 0$ tal que $\forall x \ge A, g(x) \le C \, h(x) = C \sqrt{f(x) g(x)}$. Entonces$g(x) \le C^2 f(x)$ (toma el cuadrado y divide por $g(x)$; de nuevo, asumo funciones positivas), así$g \in O(f)$, lo que va en contra de nuestra suposición inicial. La hipótesis$O(h) = O(g)$ conduce a una contradicción, que concluye la prueba.

esto parece ser cierto para las funciones "bien definidas" o para el posible "espacio / tiempo constructivo", sin embargo, se sabe que las llamadas "funciones patológicas" (por algunos) se encuentran por Blum en, por ejemplo, el teorema de Blums Gap para el cual no es el caso. por lo tanto, parece similar al concepto de, por ejemplo, diferenciación en el cálculo que funciona para las "funciones mejor comportadas" pero que se han encontrado "excepciones patológicas". no parece haber mucho estudio sistemático / posterior hasta ahora de estas "excepciones patológicas" en la teoría de la complejidad.