Big-O complejidad de c ^ n + n * (logn) ^ 2 + (10 * n) ^ c - complejidad-teoría, big-o, recurrencia

Necesito derivar la complejidad 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 que entiendo cómo derivar la complejidad Big-O de cada término individualmente, simplemente no sé cómo cambia la complejidad Big-O cuando los términos se combinan de esta manera.
Ideas?

Cualquier ayuda sería genial, gracias.

Respuestas

La notación O () considera el término más alto; Piensa en cuál dominarás para valores muy, muy grandes de n.

En tu caso, el término más alto es c^n, actualmente; Los otros son esencialmente polinomiales. Entonces, es la complejidad exponencial.

La respuesta depende de | c |

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

IF | c | > 1 es O (c ^ n)

Wikipedia es tu amigo:

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

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