Big-O complejidad de c ^ n + n * (log n) ^ 2 + (10 * n) ^ c

Question

necesito para derivar la complejidad de Big-O de esta expresión:

  

c ^ n + n * (log (n)) ^ 2 + (10 * n) ^ c

donde c es una constante y n es una variable.
Estoy bastante seguro de entender cómo derivar la complejidad de Big-O de cada término individual, sólo que no sé cómo la complejidad de Big-O cambia cuando los términos se combinan de esta manera.
Ideas?

Cualquier ayuda sería grande, gracias.

Answer 1

La notación O () considera la más alta plazo; Piense acerca de cuál va a dominar por mucho, valores muy grandes de n.

En su caso, el término más alto es c^n, en realidad; los otros son esencialmente polinomio. Por lo tanto, es la complejidad exponencial.

Answer 2

La respuesta depende de | c |

Si | c | <= 1 es de O (n * (log (n)) ^ 2)

Si | c | > 1 el mismo de la O (c ^ n)

Answer 3

Wikipedia es su amigo :

  

En el uso típico, la definición formal de notación O no se utiliza directamente; más bien, la notación O para una función f (x) se deriva por las reglas siguientes simplificaciones:

     

  
• Si f (x) es una suma de varios términos, el que tiene la mayor tasa de crecimiento se mantiene, y todos los demás omite.
  
• Si f (x) es un producto de varios factores, se omiten cualquier constante (términos en el producto que no dependen de x).