And then there's O(n alpha(n)), where alpha(n) is an inverse the Ackermann function, and which grows even more slowly than log* n. The famous union-find algorithm has this complexity.