Big-Oh impose-t-il une partition ordonnée sur l'ensemble des fonctions "habituelles"?

Question

L'exemple de Cette réponse prouve le fait que les élèves de CS - que le "Big-O" est pas une commande totale. Cependant, la plupart des temps d'exécution d'algorithme analysés à l'aide de la notation Big-Oh ne sont pas exprimés dans une forme par morceaux comme cet exemple. En fait, la plupart des algorithmes que je connais avec un temps de fonctionnement exprimé en termes de polynômes, d'exponentiations et de journaux.

Considérez la classe de fonctions définie de manière récursive qui inclut $ f (n)= C $ pour toute constante $ C $ , $ f (n)= n $ et toutes les fonctions du formulaire $ f + g, f \ CDOT g, \ journal (f), \ exp (f) $ où $ f, g $ est dans la classe. Est-ce que $ o $ imposer une partition ordonnée sur cette classe de fonctions? Les fonctions avec le même big- $ o $ la croissance est dans la même partie.

Voici mes pensées:

Notez que spécifier $ f \ CDOT g $ est réellement redondant, puisque $ f \ CDOT g=exp ( \ journal (f) + \ journal (g)) $ . Étant donné que les fonctions sont définies de manière inductive, il y a peut-être une preuve inductive.

Answer 1

Cela a été montré par Hardy dans sa monographie Commandes d'Infinity .