Existe uma complexidade entre

Existe um grau de complexidade maior que e menor que O ( n log n ) ?$O(n)$$O(n \log n)$

está entre n e n log n e é relativamente comum de se encontrar na natureza.$n \log\log n$$n$$n \log n$

Além de , há também O ( n log ∗ ( n ) ) em que log ∗ é o número de vezes que a função logaritmo deve ser aplicada para que o resultado seja menor que ou igual a 1.$O(n\log(\log(n)))$$O(n \log^*(n))$$\log^*$

Por exemplo, se você já conhece uma árvore de abrangência mínima euclidiana, a triangulação de Delaunay pode ser descoberta em $O(n\log^*(n))$ .

Mais extremamente, pode-se observar a função inversa de Ackermann , que pode ser encontrada na análise de vários algoritmos de complexidade O ( n α ( n , n ) ) . Há uma boa introdução aqui .$\alpha(n,n)$$O(n\alpha(n,n))$

Existem infinitas, desde para qualquer α < β . Então, em particular, O ( n ) = O ( n ( log n ) 0 ) ⊊ O ( n ( log n ) α ) ⊊ O ( n log n $O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$$\alpha<\beta$$O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\log n)$para qualquer .$\alpha\in (0,1)$