Sejam f e g funções de Z^+ para Z^+. Prove ou refute:
f(n) in O(g(n)) Longrightarrow 1f(n) in O(1g(n))

Passo 1

Primeiro, vamos entender o que a questão está nos pedindo. Temos duas funções, $ f(n) $ e $ g(n) $, que mapeiam números positivos para números positivos. A afirmação que precisamos analisar é:
f(n)
Aqui, estamos trabalhando com a notação Big-O, que é usada para descrever o comportamento assintótico de funções. Vamos precisar entender o que significa $ f(n) \in O(g(n)) $ e como isso se relaciona com as inversas das funções.

Passo 2

Vamos relembrar o que significa $ f(n) \in O(g(n)) $. Isso quer dizer que existe uma constante positiva $ C $ e um número $ n_0 $ tal que para todo $ n \geq n_0 $:
f(n) in O(g(n))
Em outras palavras, $ f(n) $ cresce no máximo tão rápido quanto $ g(n) $, até uma constante multiplicativa.

Passo 3

Agora, precisamos analisar o que significa $ \frac{1}{f(n)} \in O\left(\frac{1}{g(n)}\right) $. Isso significa que existe uma constante positiva $ K $ e um número $ m_0 $ tal que para todo $ n \geq m_0 $:
1f(n) in O(1g(n))
Queremos ver se essa relação é verdadeira dado que $ f(n) \in O(g(n)) $.

Passo 4

Vamos usar a condição inicial $ f(n) \leq C \cdot g(n) $ para encontrar uma relação entre $ \frac{1}{f(n)} $ e $ \frac{1}{g(n)} $. Se $ f(n) \leq C \cdot g(n) $, então:
f(n) <= C cdot g(n)
Isso significa que $ \frac{1}{f(n)} $ é pelo menos $ \frac{1}{C} $ vezes $ \frac{1}{g(n)} $.

Passo 5

Observamos que a desigualdade obtida no passo anterior vai na direção oposta à que queremos para $ \frac{1}{f(n)} \in O\left(\frac{1}{g(n)}\right) $. Na verdade, temos:
1f(n) in O(1g(n))
Isso indica que $ \frac{1}{f(n)} $ pode crescer mais rápido do que $ \frac{1}{g(n)} $, o que contraria a definição de Big-O que requer $ \frac{1}{f(n)} $ ser limitada superiormente por uma constante vezes $ \frac{1}{g(n)} $.

Passo 6

Vamos considerar um exemplo para ilustrar isso. Suponha que $ f(n) = n $ e $ g(n) = n $. Claramente, $ f(n) \in O(g(n)) $ porque $ f(n) = g(n) $.
Agora, vejamos as inversas:
f(n) = n
g(n) = n
Neste caso, $ \frac{1}{f(n)} = \frac{1}{g(n)} $, então a afirmação parece verdadeira. No entanto, se escolhermos $ f(n) = n $ e $ g(n) = n^2 $, onde $ f(n) \in O(g(n)) $, então:
f(n) in O(g(n))
f(n) = g(n)
Aqui, $ \frac{1}{f(n)} = \frac{1}{n} $ não está em $ O\left(\frac{1}{n^2}\right) $, já que $ \frac{1}{n} $ decai mais devagar do que $ \frac{1}{n^2} $.

Passo 7

Com base no exemplo acima, podemos concluir que a afirmação original nem sempre é verdadeira. Embora $ f(n) \in O(g(n)) $ sugira que $ f(n) $ não cresce mais rápido que $ g(n) $, as inversas das funções podem ter comportamentos diferentes, especialmente em relação à taxa de decaimento.

Resposta

A afirmação é falsa. Se $ f(n) \in O(g(n)) $, não necessariamente $ \frac{1}{f(n)} \in O\left(\frac{1}{g(n)}\right) $.

Exercícios relacionados