Sejam
e
funções de
para
. Prove ou refute:
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 é:
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 $:
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 $:
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:
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:
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:
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:
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) $.