Complete classification of complexity classes / infinite approaching sequences

Question

http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

For complexity as seen in the above link, complexity classes can be log, polynomial, exp, or composition of any of these function. It is tempting to see if all complexity classes can be made so.

This is certainly not the case because we have Ackermann function. Then is it possible to expand the list to find a set of functions and say "all complexity classes can be made from compositions of functions from such a set" ?

Put the question in another way, consider the collection of all infinite approaching integer sequences, let me denote any sequence $a_n$ by a single letter $A$, define $A \le B$ if $O(A) \le O(B)$, then we get an ordered set of equivalence classes of sequences. The question is: how does this set look like? A dictionary ordered version of some power of $R$?

Answer 1

Let us write $f\le_O g$ if $O(f)\le O(g)$, i.e., $f=O(g)$.

There is much to say about this order, but I'll stick to whether it looks like your suggestion:

A dictionary ordered version of some power of R?

1. As for dictionary order: We do have a similarity in that there is density: if $f<_O g$ then there is some $h$ with $f<_O h<_O g$.

   Note $f\le c\cdot g$ means $\log f\le^+ \log g$ where $\le^+$ means "$\le$ up to an additive constant", so we can consider $\le^+$ instead.

   If $f<^+ g$ then we can find an $h$ with $f<^+ h<^+ g$ by: let $f=h$ except when otherwise noted; for each $c$, look for an $n=n_c>n_{c-1}$ where $g(n)-f(n)>2c$ (which must exist) and let $h(n)=f(n)+c$. Then we see $h\not\le^+ f$ and $g\not\le^+ h$.

2. As for "power of $R$", assuming "power" means "power set", this doesn't seem to fit:

   1. if by $R$ you mean $\mathbb R$, the real numbers, then since each $f:\mathbb N\rightarrow\mathbb N$, the cardinality of the induced partial order on $\mathbb N^{\mathbb N}$ is $\le 2^{\aleph_0}$ (actually equal to $2^{\aleph_0}$) whereas the power set of $\mathbb R$ has cardinality $2^{2^{\aleph_0}}$;
   2. if by $R$ you mean $\mathcal R$, the set of recursive (computable) functions, then the power set has cardinality $2^{\aleph_0}$ but there are only countably many $=_O$-classes of computable functions.