POSCOMP 2019: Questão 22 Resolvida (Notações Assintóticas)

Questão

Considere as seguintes funções:

$$\begin{gather}f(n)=2^n\\g(n)=n!\\h(n)=n^{\log n}\end{gather}$$

Assinale a alternativa correta a respeito do comportamento assintótico de $f(n)$, $g(n)$ e $h(n)$.

• (A) $f(n)=O(g(n));g(n)=O(h(n))$
• (B) $f(n)=\Omega(g(n));g(n)=O(h(n))$
• (C) $g(n)=O(f(n));h(n)=O(f(n))$
• (D) $h(n)=O(f(n));g(n)=\Omega(f(n))$
• (E) Nenhuma das anteriores.

Resolução

Observe que a questão em si consiste basicamente em verificar qual função é assintoticamente maior ou menor que a outra.

Isto é, a partir de qual valor de $n$ suficientemente grande uma função será sempre menor ou maior em comparação com as demais.

Na prática, se soubermos ordenar as funções assintoticamente, podemos resolver o problema.

No blog, já foi abordado que a complexidade fatorial $n!$ é pior que a exponencial $2^n$ e que, consequentemente, $2^n=O(n!)$.

Isso elimina as alternativas B e C, já que é falso dizer que $f(n)=\Omega(g(n))$ (isso seria equivalente a dizer que assintoticamente $2^n \geq n!$, que é falso) e também é falso dizer $g(n)=O(f(n))$.

Todavia, a função $n^{\log n}$ pode ser um pouco confusa (especialmente se levarmos em conta que não foi dado a base do logaritmo, embora, nesse caso, a informação não seja relevante e assumiremos que a base é 2).

Por causa isso, utilizaremos a seguinte tabela (casas decimais foram truncadas), para verificarmos a partir de qual valor de $n$ uma função é maior ou menor que a outra assintoticamente.

$$n$$	$$h(n)=n^{\log_2 n}$$	$$f(n)=2^n$$	$$g(n)=n!$$
1	1	2	1
2	2	4	2
3	5	8	6
4	16	16	24
5	41	32	120
6	102	64	720
7	235	128	5040
8	512	256	40320
9	1058	512	362880
10	2098	1024	3628800
11	4005	2048	39916800
12	7393	4096	4,79×108
13	13245	8192	6,23×109
14	23105	16384	8,72×1010
15	39342	32768	1,31×1012
16	65536	65536	2,09×1013
17	107007	131072	3,56×1014
18	171550	262144	6,40×1015

Observe que a partir do valor $n=17$, já é possível definir a ordem de crescimento das funções.

Por meio dos dados da tabela, verificamos que as funções podem ser colocadas na seguinte ordem (da menor para a maior) em termos de crescimento assintótico: $n^{\log n}$, $2^n$ e $n!$. Portanto, é falso afirmar que $g(n)=O(h(n))$, já que $g(n)=n!$ é assintoticamente maior que $h(n)=n^{\log n}$. Isso elimina a alternativa A.

Analisando a alternativa D, vemos que $h(n)=O(f(n))$ é verdadeiro (isto é, $n^{\log n}=O(2^n)$) e também é verdadeiro dizer que $g(n)=\Omega(f(n))$ (ou seja, $n!=\Omega(2^n)$), pois a função exponencial é assintoticamente menor que a função fatorial.

Em outras palavras, a alternativa correta é a D.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.