Need clarification on big o notation

[jjwooyoung]

I read in my textbook that within a function, the bigger complexity overwhelms the smaller one.

Ex.

foo()
   for(...)
      for(...)

   for(...)

This function is O(n^2) and O(n). But the final complexity is O(n^2).

Now, what I'm confused about is this: if that's the case, why do I see complexities like O(n log n)? Example: merge sort is O(n log n) - O(log n) for splitting and O(n) for merging back

[Ispil]

Well, it overwhelms in regards to addition. Multiplication, not so much. If it were n+log n, that would simplify down to O(n). But, since it's a product, it doesn't simplify like that. Otherwise, you could claim n^3=n^2*n=O(n^2), n^2=n^(3/2)*n^(1/2)=O(n^(3/2)), and so on. It would be silly. Also, in your example, it is incredibly dependent on what's inside those for loops that determines the complexity.

foo(int n)
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            //code
    for(int k = 0; k < n; ++k)
        //code
}

does not have the same complexity as this:

{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < 10; ++j)
            //code
    for(int k = 0; k < n; ++k)
        //code
}

which does not have the same complexity as this:

{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n*i; ++j)
            //code
    for(int k = 0; k < n; ++k)
        //code
}

and certainly does not have the same complexity as this:

{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            //code
    for(int k = 0; k < n*n*n; ++k)
        //code
}

so be very careful on that point.

[jjwooyoung]

Can you give me an example of when it's an addition vs multiplication?

[Ispil]

What would be the difference between the big O of n+log(n) and n*log(n)?

[htirwin]

This is a long answer, but the following paragraph alone is enough to clarify what Big-O means, so if nothing else, just focus on understanding that part.

O( f(n) ) is actually a set of functions. The running time as a function of the input size of an algorithm, T(n), is in the set O( f(n) ) if for all natural numbers n, cf(n) + d is greater than or equal to T(n) for some constants c and d.

It's important to note we are talking about for all n, but the constants c and d must be fixed. What this captures is the growth rate of the function. As n gets larger and larger, the fastest growing terms dominate.

Back to your question, why the final complexity is O(n^2) and not O(n^2+n)? The answer is that n^2 + n, and n^2 both belong to the set O(n^2), because for example setting c=2,d=1, n^2 + n <= 2n^2 + 1 for all n. In fact, O(n^2+n) is just another name for O(n^2); they are the same exact sets, so it's simpler to just call it O(n^2).

In general, say you have T(n) = g(n) + h(n), and h(n) <= g(n), then it's easy to see that g(n) + h(n) <= 2g(n). Now that you have T(n) < 2g(n), from the definition of Big-O, it's easy to then see why T(n) is in O(g(n)), for example, you can choose c=4, d=0, in which case 2g(n) <= 4g(n).

In the case of multiplication, T(n) = g(n)*h(n), if you know h(n) <= g(n), then you know T(n) <= g(n)*g(n). So you know T(n) is in O(g(n)^2). But remember this is an upper bound. If h(n) < g(n) to within a multiplicative and additive constant, then the set O(g(n)^2 ) is not equal to O(h(n)*g(n)). T(n) belongs to both sets, but O(h(n)) corresponds to a "tighter bound". Usually, when asked which complexity class T(n) belongs to, there is some unstated intention that they want you to give the set corresponding to the tightest upper bound.

It can be confusing because the '=' symbol that people sometimes use in Big-O notation doesn't mean equals. For example, some might write this, O(n) = O(n^2), 1=O(n^2), which are obviously not true when = means equals. The true meaning is that O(n) is a subset of O(n^2) and 1 is an element of O(n^2), which are both true statements. It's a horrible, horrible abuse that should never have been adopted.

There are also the sets Big-Theta(f(n)), and Big-Omega(f(n)), which are the sets containing all functions that have the same growth rate, and a larger or equal growth rate respectively. Big-O is commonly incorrectly used, when people actually mean to use Big-Theta.

I think teachers trying to get across the important concepts of asymptomatic time complexity often end up redefining what it means in a dumbed down simple way. But the ultimate result may end up being a lifetime of confusion and false knowledge for the poor student who was lied to like a child too young to hear the truth. It doesn't help that these white lies are also contradictory and ambiguous.

[jjwooyoung]

@Ispil: No when is it a multiplication type big o vs an addition type big o

[Ispil]

...there isn't an "additive type." When I said that it overwhelms in regards to addition, I meant that n overwhelms log n in the equation n + log n, but this doesn't work in the case of multiplication, n * log n.

[helios]

Can you give me an example of when it's an addition vs multiplication?

Addition implies that the algorithm contains one loop followed by another loop.

for (int i = 0; i < f(n) i++){ ... }
for (int i = 0; i < g(n) i++){ ... }
//O(f(n) + g(n)) (assume ellipses contain only O(1) operations) 

Multiplication implies that the algorithm contains one loop nested in another loop.

for (int i = 0; i < f(n) i++){
    for (int j = 0; j < g(n) j++){ ... }
}
//O(f(n) * g(n)) (assume ellipsis contains only O(1) operations)