Análisis de Big-O con funciones dentro de las funciones

Question

Estoy confundido acerca de cómo funciona Big-O cuando se trata de funciones dentro de funciones (al analizar el peor de los casos). Por ejemplo, lo que si tiene algo como:

for(int a = 0; a < n; a++) 
{ 
    *some function that runs in O(n*log(n))* 
    for(int b = 0; b < n; b++) 
    { 
     *do something in constant time* 
    } 
} 

haría todo este bloque plazo en O (n^2 * log (n)), porque dentro del primer bucle, tiene una O (n) y un O (n * log (n)), entonces O (n * log (n)) es mayor, y por lo tanto, el que tomamos? ¿O es O (n^3 * log (n)) porque tiene un O (n) y un O (n * log (n)) dentro del ciclo for externo?

¡Se agradece cualquier ayuda! ¡Gracias!

Answer 1

Es

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N)) 
           = O(N) * O(N lg N) 
           = O(N^2 lg N) 

Debido a que tiene O(N) iteraciones de una función O(N lg N) y O(N) operaciones de tiempo constante. El O(N lg N) + O(N) se simplifica a O(N lg N) porque O(N lg N) > O(N).

Answer 2

En el cálculo de este tipo de complejidad que debería añadir línea o funciones secuenciales y se multiplican funciones anidadas.

Por ejemplo, esto sería O(n):

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed) 
for (int i = 0; i < n; i++) 
{ 
    /* something constant */ 
} 
for (int j = 0; j < n; j++) 
{ 
    /* something constant */ 
} 

Pero cuando se anidan las funciones, multiplicar su complejidad:

// O(n) * O(n) = O(n^2) 
for (int i = 0; i < n; i++) 
{ 
    for (int j = 0; j < n; j++) 
    { 
     /* something constant */ 
    } 
} 

Su ejemplo es una combinación - tienes algunas operaciones secuenciales anidado dentro de otra función.

// this is O(n*logn) + O(n), which is O(n*logn) 
*some function that runs in O(n*log(n))* 
for(int b = 0; b < n; b++) 
{ 
    *do something in constant time* 
} 

// multiplying this complexity by O(n) 
// O(n) * O(n*logn) 
for(int a = 0; a < n; a++) 
{ 
    // your O(n*logn) 
    // your b loop 
}