Exercícios - Relação de Equivalência

3. Sejam f, g duas funções de Z⁺ para Z⁺, ambas monótonas crescentes. Define-se a relação ≼ entre funções f e g de seguinte maneira: f ≼ g ⟷ ∃C ∈ ℝ, n₀ ∈ ℕ \n > n₀ : f(n) ≤ Cg(n) Ainda define-se a relação ∼ entre funções f e g de seguinte maneira: f ∼ g ⟷ f ≼ g ∧ g ≼ f Mostre que ∼ é uma relação de equivalência. Observação Intuitivamente, a relação f ∼ g quer dizer que f e g têm a mesma ordem, o que corresponde à notação f ∈ Θ(g), a notação Teta grande. Mas você não pode usar este fato na sua prova, que deve usar a definição da relação de ordem ‘≼’ como ponto de partida. Uma questão natural que me surgiu discutindo o comportamento assintótico de funções era se a notação O Grande é uma ordem total. Porém, não é o caso na definição original, por causa de alguns contra-exemplos patológicos e extremamente artificiais. No entanto, adicionando a condição de que f e g são monótonas crescentes elimina esses contra-exemplos, e a relação f ≼ g se torna um ordem total (para cada par de funções f, g, ou f ≼ g ou g ≼ f). Resumo: para funções monótonas crescentes, a notação Teta grande é uma relação de equivalência, enquanto a notação O grande é uma ordem total.