Complexidade big-o de c^n + n*(logn)^2 + (10*n)^c

Question

Eu preciso derivar a complexidade grande dessa expressão:

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

onde C é uma constante e n é uma variável.
Tenho certeza de que entendo como derivar a complexidade Big-O de cada termo individualmente, simplesmente não sei como a complexidade Big-O muda quando os termos são combinados assim.
Ideias?

Qualquer ajuda seria ótima, obrigado.

Answer 1

A notação o () considera o termo mais alto; pense em qual deles dominará para valores muito, muito grandes de n.

No seu caso, o termo mais alto é c^n, na realidade; Os outros são essencialmente polinomiais. Então, é complexidade exponencial.

Answer 2

A resposta depende de | C |

Se | C | <= 1 é o (n*(log (n))^2)

Se | C | > 1 é o (c^n)

Answer 3

Wikipedia é seu amigo:

No uso típico, a definição formal de notação O não é usada diretamente; Em vez disso, a notação O para uma função f (x) é derivada pelas seguintes regras de simplificação:

• Se f (x) é uma soma de vários termos, a maior taxa de crescimento é mantida e todos os outros omitidos.
• Se f (x) é um produto de vários fatores, quaisquer constantes (termos no produto que não dependem de x) serão omitidos.