Big-Oh impone una partizione ordinata sul set delle funzioni "usuali"?

Question

L'esempio in Questa risposta dimostra il fatto familiare agli studenti CS - che il "Big-O" è non un ordine totale. Tuttavia, la maggior parte dei tempi di funzionamento dell'algoritmo analizzati utilizzando la notazione Big-Oh non sono espressi in forma a tratti come questo esempio. Infatti, la maggior parte degli algoritmi ho familiarità con un tempo di esecuzione espresso in termini di polinomi, esponenti e tronchi.

Considera la classe di funzioni definita in modo ricorsivo che include $ f (n)= c $ per qualsiasi costante $ c $ , $ f (n)= n $ , e qualsiasi funzione del modulo $ f + g, f \ cdot g, \ log (f), \ exp (f) $ dove $ f, G $ sono in classe. $ o $ Imporre una partizione ordinata su questa classe di funzioni? Le funzioni con la stessa big- $ o $ la crescita è nella stessa parte.

Ecco i miei pensieri:

Nota che specificando $ f \ cdot G $ è in realtà ridondante, poiché $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Poiché le funzioni sono definite induttivamente, forse c'è una prova induttiva.

Answer 1

Questo è stato dimostrato da Hardy nella sua monografia ordini di infinito .