Big-Oh impõe uma partição ordenada no conjunto das funções "usuais"?

Question

O exemplo em Esta resposta prova o fato familiar para os alunos do CS - que o "Big-O" é não é um pedido total. No entanto, a maioria dos tempos de execução de algoritmo analisada usando a notação Big-Oh não são expressas em forma por partes como este exemplo. Na verdade, a maioria dos algoritmos que estou familiarizado com ter um tempo de execução expresso em termos de polinômios, exponenciações e logs.

Considere a classe de funções recursivamente definidas que inclui $ F (n)= C $ para qualquer constante $ c $ , $ f (n)= n $ e quaisquer funções do formulário $ f + g, f \ CDOT g, \ log (f), \ exp (f) $ onde $ f, g $ estão na classe. $ o $ Imponha uma partição ordenada nesta classe de funções? As funções com a mesma grande classe="recipiente de matemática"> $ o $ o crescimento é na mesma peça.

Aqui estão meus pensamentos:

Observe que especificar $ f \ cdot g $ é realmente redundante, já que $ f \ cdot g=exp ( \ log (f) + \ log (g)) $ . Como as funções são indutivamente definidas, talvez haja uma prova indutiva.

Answer 1

Isso foi mostrado por Hardy em sua monografia ordens de infinito .