MO417 - Questão para a prova oral

Número: 022

Enunciado: Assumindo que f(n) e g(n) são funções assintoticamente positivas, avalie as seguintes afirmações sobre propriedades das classes de funções.

I. A reflexividade se aplica a todas as classes de funções: O, o, Ω, ω e Θ.

f(n) ∈ O(f(n)),       f(n) ∈ o(f(n)),       f(n) ∈ Ω(f(n)),       f(n) ∈ ω(f(n)),       f(n) ∈ Θ(f(n)).

II. A simetria se aplica à classe Θ.

f(n) ∈ Θ(g(n)) se e somente se g(n) ∈ Θ(f(n))

III. A transitividade se aplica a todas as classes de funções: O, o, Ω, ω e Θ.

Se f(n) ∈ O(g(n)) e g(n) ∈ O(h(n)) então f(n) ∈ O(h(n))

Se f(n) ∈ o(g(n)) e g(n) ∈ o(h(n)) então f(n) ∈ o(h(n))

Se f(n) ∈ Ω(g(n))) e g(n) ∈ Ω(h(n)) então f(n) ∈ Ω(h(n))

Se f(n) ∈ ω(g(n)) e g(n) ∈ &omega(h(n)) então f(n) ∈ ω(h(n))

Se f(n) ∈ Θ(g(n)) e g(n) ∈ Θ(h(n)) então f(n) ∈ Θ(h(n))

Assinale a alternativa que indica todas as afirmações corretas:

  1. I está correta

  2. I e II estão corretas

  3. I e III estão corretas

  4. II e III estão corretas

  5. NDA

Autor(a): Celina d' Ávila Samogin