Quais das seguintes alternativas são verdadeiras para todas as funções f(n) positivas? Dica: tente fazer f(n) sendo polinomial, exponencial e logarítmica, quando couber.
a. f\left(n^{2}\right)=\theta\left(f(n)^{2}\right), quando f(n) é polinomial
b. f\left(n^{2}\right)=o\left(f(n)^{2}\right)
c. f\left(n^{2}\right)=O\left(f(n)^{2}\right), quando f(n) é exponencial
d. f\left(n^{2}\right)=\Omega\left(f(n)^{2}\right)

Passo 1

O enunciado nos pede para verificar quais das afirmações a–d valem para toda função positiva f(n). A dica sugere testar três casos usuais de crescimento:
  1. f(n) polinomial, por exemplo f(n)=n^k.
  2. f(n) exponencial, por exemplo f(n)=a^n com a>1.
  3. f(n) logarítmica, por exemplo f(n)=\log n.

Passo 2

Analisando a afirmação (a):
f(n^2)=\Theta\bigl(f(n)^2\bigr)\quad\text{quando \(f\) é polinomial.}é
  • Se f(n)=n^k, então f(n^2)=(n^2)^k=n^{2k} e f(n)^2=(n^k)^2=n^{2k}.
  • Logo f(n^2)=\Theta\bigl(f(n)^2\bigr) de fato vale para funções polinomiais.
    Mas se f(n)=\log n, então f(n^2)=2\log n e f(n)^2=(\log n)^2, e 2\log n não é \Theta((\log n)^2).
    Portanto (a) não vale para toda f, apenas para polinomiais.

Passo 3

Analisando a afirmação (b):
f(n^2)=o\bigl(f(n)^2\bigr).
  • Para f(n)=n^k, temos f(n^2)=n^{2k} e f(n)^2=n^{2k}, logo f(n^2) não é o(f(n)^2) \Theta).
  • Para f(n)=a^n, f(n^2)=a^{n^2} cresce muito mais rápido que f(n)^2=a^{2n}, então tampouco é o.
  • Para f(n)=\log n, f(n^2)=2\log n e f(n)^2=(\log n)^2; aqui 2\log n também não é o((\log n)^2) O((\log n)^2) mas não estritamente menor).
    Logo (b) é falsa em todos os três casos.

Passo 4

Analisando a afirmação (c):
f(n^2)=O\bigl(f(n)^2\bigr)\quad\text{quando \(f\) é exponencial.}é
  • Se f(n)=a^n, então f(n^2)=a^{n^2} e f(n)^2=a^{2n}.
  • A razão \dfrac{f(n^2)}{f(n)^2}=a^{n^2-2n}\to\infty, portanto não existe constante que faça a^{n^2}\le C\,a^{2n} para n grande.
    Logo (c) também é falsa mesmo no caso exponencial.

Passo 5

Analisando a afirmação (d):
f(n^2)=\Omega\bigl(f(n)^2\bigr).
  • Para f(n)=n^k, f(n^2)=n^{2k} e f(n)^2=n^{2k}, então vale (é \Omega).
  • Para f(n)=a^n, f(n^2)=a^{n^2} cresce muito mais rápido que a^{2n}, então também vale ( \Omega).
  • Mas para f(n)=\log n, temos f(n^2)=2\log n e f(n)^2=(\log n)^2, e 2\log n não domina (\log n)^2 (falha o \Omega).
    Portanto (d) falha no caso logarítmico.

Resposta

Nenhuma das alternativas a, b, c ou d vale para todas as funções positivas f(n).

Exercícios relacionados