Big-O Analysis with Functions Inside Functions

Question

I am confused about how Big-O works when working with functions inside functions (when analyzing the worst case). For example, what if you have something like:

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*
    }
}

Will this whole block work in O (n ^ 2 * log (n)), because in the first for loop you have O (n) and O (n * log (n)), so O (n * log ( n)) more, and therefore the one we take? Or is it O (n ^ 3 * log (n)) because you have O (n) and O (n * log (n)) inside the outer loop?

Any help is appreciated! Thank!

Answer 1

it

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)

O(N) O(N lg N) O(N) . O(N lg N) + O(N) O(N lg N), O(N lg N) > O(N).

Answer 2

.

, 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 */ 
}

, :

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

- - , .

// 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
}