Big-O analysis with functions within functions

Question

I'm confused about how Big-O works when dealing with functions within functions (when analyzing 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*
    }
}

Would this entire block run in O(n^2*log(n)), because within the first for loop, you have an O(n) and an O(n*log(n)), so O(n*log(n)) is greater, and therefore the one we take? Or is it O(n^3*log(n)) because you have an O(n) and an O(n*log(n)) within the outer for loop?

Any help is appreciated! Thanks!

Answer 1

It's

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)

Because you have O(N) iterations of an O(N lg N) function and O(N) constant time operations. The O(N lg N) + O(N) simplifies to O(N lg N) because O(N lg N) > O(N).

Answer 2

When calculating this type of complexity you should add inline or sequential functions and multiply nested functions.

For example, this would be 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 */ 
}

But when the functions are nested, multiply their complexity:

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

Your example is a combination - you've got some sequential operations nested inside another function.

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