Escreva as seguintes funcões em notação
,
, googol,
.
Resposta:
; googol
.
Resposta:
Passo 1
O enunciado pede para expressar várias funções em notação assintótica O, ou seja, encontrar para cada f(n) uma função g(n) mais simples tal que f(n)=O(g(n)). O conteúdo envolvido é o conceito de complexidade assintótica (Big-O), onde desprezamos constantes e termos de menor ordem conforme n cresce.
Passo 2
Pela definição de Big-O, se f(n) é composta por soma de termos, o termo de maior crescimento domina. No caso de f(n)=n³−1, o termo dominante é n³, pois −1 é constante. Logo, n³−1=O(n³).
Passo 3
Para f(n)=n²+2
log
n, note que log
n cresce muito mais devagar que n². Assim, n² é o termo dominante, e 2
log
n=O(log
n)=o(n²). Portanto, n²+2
log
n=O(n²).
log
n, note que log
n cresce muito mais devagar que n². Assim, n² é o termo dominante, e 2
log
n=O(log
n)=o(n²). Portanto, n²+2
log
n=O(n²).
Passo 4
Na função f(n)=3
nⁿ+5·2ⁿ, compare nⁿ e 2ⁿ. Sabemos que nⁿ cresce muito mais rápido que 2ⁿ conforme n→∞. Então 5·2ⁿ=O(2ⁿ)=o(nⁿ) e 3
nⁿ domina. Assim, 3
nⁿ+5·2ⁿ=O(nⁿ).
nⁿ+5·2ⁿ, compare nⁿ e 2ⁿ. Sabemos que nⁿ cresce muito mais rápido que 2ⁿ conforme n→∞. Então 5·2ⁿ=O(2ⁿ)=o(nⁿ) e 3
nⁿ domina. Assim, 3
nⁿ+5·2ⁿ=O(nⁿ).
Passo 5
Para (n−1)ⁿ+nⁿ⁻¹, observe que (n−1)ⁿ≤nⁿ e nⁿ⁻¹=nⁿ/n=O(nⁿ). A soma de duas funções O(nⁿ) continua sendo O(nⁿ). Logo, (n−1)ⁿ+nⁿ⁻¹=O(nⁿ).
Passo 6
Termos que não dependem de n—como googol (10¹⁰⁰) ou 100(100(100¹⁰⁰))—são constantes. Qualquer constante C satisfaz C=O(1).
Resposta
n{3}-1=O(n{3}) ; n^{2}+2\log n=O(n^{2}) ; 3n{n}+5\cdot2{n}=O(n^{n}) ; (n-1){n}+n{n-1}=O(n^{n}) ; googol,(10^{100})=O(1) ; 100{100{100^{100}}}=O(1)