¿Big-OH impone una partición ordenada en el conjunto de las funciones "habituales"?

Question

El ejemplo en Esta respuesta demuestra que el hecho es familiar para los estudiantes de CS, que la "BIG-O" es No es un pedido total. Sin embargo, la mayoría de los tiempos de ejecución del algoritmo analizados utilizando la notación de BIG-OH no se expresan en forma a prueba de este ejemplo. De hecho, la mayoría de los algoritmos en la que estoy familiarizado con tener un tiempo de ejecución expresado en términos de polinomios, exponentes y registros.

Considerar la clase de funciones definidas recursivamente definidas que incluyen $ f (n)= C $ para cualquier constante $ C $ , $ f (n)= n $ , y cualquier función del formulario $ f + g, f \ CDOT G, \ log (f), \ exp (f) $ donde $ f, g $ están en la clase. ¿ $ o $ imponer una partición ordenada en esta clase de funciones? Las funciones con el mismo Big- $ o $ El crecimiento está en la misma parte.

Aquí están mis pensamientos:

Tenga en cuenta que especificar $ f \ cdot g $ es realmente redundante, desde $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Dado que las funciones se define inductivamente, quizás haya una prueba inductiva.

Answer 1

Esto fue mostrado por Hardy en su monografía órdenes de infinito .