Classification of all "Big O equivalence classes"

492 Views Asked by At

Given functions $f$, $g$, $f = \Theta(g)$ defines an equivalence relation. The equivalence classes of this relation are intensively used in computer science. See for example https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities for a list of equivalence classes. Now my question is:

Is there a complete classification of all equivalence classes?

As a bonus question: Is there a classification of all equivalence classes of the relation $f \sim g$ (as defined in https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations)?