¿Cuál es el método adecuado para encontrar el orden de crecimiento para esta función?

Question

2 ^ n + 6n ^ 2 + 3n

Supongo que es solo O (2 ^ n), usando el término de orden más alto, pero ¿cuál es el enfoque formal para probar esto?

Answer 1

Puede probar que 2 ^ n + n ^ 2 + n = O (2 ^ n) utilizando límites en el infinito. Específicamente, f (n) es O (g (n)) if lim (n- > inf.) F (n) / g (n) es finito.

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

Dado que tiene inf / inf, una forma indeterminada , puede usar la regla de L'Hopital y diferencia el numerador y el denominador hasta que obtengas algo puedes trabajar con:

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

El límite es 1, entonces 2 ^ n + n ^ 2 + n es de hecho O (2 ^ n) .

Answer 2

Por favor vea:

Tarea de notación Big O - Análisis de algoritmo de fragmento de código?

Big O, ¿cómo se calcula / aproxima?

Can alguien por favor explique la diferencia entre la notación Big-O y Little-O?

¿Big-O para niños de ocho años? (no debe ser insultante)