Prove que
para
, mostrando a existência das constantes
e
da definição.
Passo 1
Beleza, vamos lá! O que a gente tem aqui é um exercício de Análise de Algoritmos, especificamente sobre a notação Big-O. A ideia é provar que a função $ \frac{1}{n-1000} $ está no Big-O de $ \frac{1}{n} $ para $ n > 1000 $. Para isso, a gente precisa encontrar duas constantes, $ C $ e $ n_0 $, que satisfazem a definição de Big-O.
Passo 2
Primeiro, vamos relembrar o que significa $ f(n) \in O(g(n)) $. Isso quer dizer que existe uma constante positiva $ C $ e um ponto $ n_0 $ a partir do qual $ f(n) $ nunca vai crescer mais rápido que $ C $ vezes $ g(n) $. Formalmente:
No nosso caso, $ f(n) = \frac{1}{n-1000} $ e $ g(n) = \frac{1}{n} $.
Passo 3
Vamos substituir $ f(n) $ e $ g(n) $ na definição:
Simplificando, multiplicamos ambos os lados por $ n(n-1000) $ (que é positivo para $ n > 1000 $):
Passo 4
Agora, queremos isolar $ C $. Vamos rearranjar a inequação:
Subtraindo $ Cn $ de ambos os lados:
Fatorando $ n $:
Passo 5
Queremos uma relação que funcione para todo $ n > 1000 $. Vamos escolher $ C $ de forma que $ 1 - C $ seja negativo, já que $ n > 1000 $ e queremos que a inequação seja verdadeira. Por exemplo, se escolhermos $ C = 2 $:
Isso simplifica para:
Passo 6
Então, com $ C = 2 $ e $ n_0 = 2000 $, a inequação $ \frac{1}{n-1000} \leq 2 \cdot \frac{1}{n} $ vale para todo $ n \geq 2000 $. Assim, essas constantes satisfazem a definição de Big-O.
Resposta
Portanto, $ \frac{1}{n-1000} \in O\left(\frac{1}{n}\right) $ para $ n > 1000 $ com as constantes $ C = 2 $ e $ n_0 = 2000 $.