O que é o método adequado para ir sobre encontrar a ordem de crescimento para esta função?

Question

2 ^ n + 6n + 2 ^ 3n

Eu acho que é apenas O (2 ^ n), usando o termo de ordem mais alta, mas o que é a abordagem formal para ir para provar isso?

Answer 1

Você pode provar que 2^n + n^2 + n = O(2^n) usando limites no infinito. Especificamente, f(n) é O(g(n)) se lim (n->inf.) f(n)/g(n) é finito.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

Uma vez que você tem inf / inf, um indeterminado forma , você pode usar regra de L'Hopital e diferenciar o numerador eo denominador até conseguir algo você pode trabalhar com:

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

O limite é 1, então 2^n + n^2 + n é realmente O(2^n).

Answer 2

Por favor, veja:

Big O Notation Homework -? Fragmento de código Análise de Algoritmo

Big O, como você calcula / aproximá-la?

Can alguém por favor explicar a diferença entre Big-o e Little-o notação?

Big-O para Eight Year Olds? (não pretende ser insultando)