Escreva as seguintes funcões em notação O: n^3-1, n^2+2 log n, 3 n^n+5 cdot 2^n, (n-1)^n+n^n-1, googol, 100^100^100^100.
Resposta: n^3-1=O(n^3) ; n^2+2 log n=O(n^2) ; 3 n^n+5.2^n=O(n^n) ;(n-1)^n+n^n-1=O(n^n); googol =10^100=O(1) ; 100^100^100^100=O(1).

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²).

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ⁿ).

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)

Exercícios relacionados