Onde as seguintes funções se encaixam nessa hierarquia? (Mostre a sua solução) (a) π(n) = nlnn. Esta função define o número de primos menor ou igua...

Para comparar as funções e determinar onde elas se encaixam na hierarquia, podemos usar a dica fornecida: ef(n) ≺ eg(n) ⇐⇒ limn→∞(f(n)− g(n)) = −∞. (a) π(n) = nlnn. Podemos comparar essa função com a função n. Temos que limn→∞(nlnn - n) = limn→∞(lnn / (1/n)) = limn→∞(lnn / n) = limn→∞(1 / n) = 0. Portanto, π(n) ≺ n. (b) e√logn. Podemos comparar essa função com a função n. Temos que limn→∞(e√logn - n) = limn→∞(e√logn / n) = limn→∞(e^(√logn - ln(n))) = limn→∞(e^(√logn / ln(n))) = ∞. Portanto, n ≺ e√logn. Assim, temos que a função π(n) = nlnn é assintoticamente menor que n, mas assintoticamente maior que e√logn. E a função e√logn é assintoticamente maior que n.