Prove que 1n-1000 in O(1n) para n>1000, mostrando a existência das constantes n0 e C 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:
f(n) in O(g(n))
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:
f(n)
Simplificando, multiplicamos ambos os lados por $ n(n-1000) $ (que é positivo para $ n > 1000 $):
g(n)

Passo 4

Agora, queremos isolar $ C $. Vamos rearranjar a inequação:
C
Subtraindo $ Cn $ de ambos os lados:
n <= Cn - 1000C
Fatorando $ n $:
Cn

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 $:
n > 1000
Isso simplifica para:
C

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 $.

Exercícios relacionados