What is the product of O(n) and O(log n)?

No, it doesn't really make sense to do that. The Big-O function yields sets of functions and sets cannot be multiplied together.

More generally, you don't normally perform any operations on O(...) results. There's no adding them, subtracting them, multiplying them. No algebra. O(...) typically shows up at the conclusion of a proof: "Based on the analysis above, I conclude that the worst case complexity of Finkle's Algorithm is O(whatever)." It doesn't really show up in the middle where it one might subject it to algebraic manipulation.

(You could perform set operations, I suppose. I've never seen anybody do that.)

To formalise what it means to do O(n) * O(log n), let's make the following definition:

A function f is in O(n) * O(log n) if and only if it can be written as a product f(n) = g(n) h(n) where g is in O(n) and h is in O(log n).

Now we can prove that the set O(n) * O(log n) is equal to the set O(n log n) by showing that the functions in both sets are the same:

• Given g in O(n) and h in O(log n), there are N_g, c_g, N_h, c_h such that for all n >= max(N_g, N_h) we have |g(n)| <= c_g n and |h(n)| <= c_h log n. It follows that |g(n) h(n)| <= c_g c_h n log n, and so max(N_g, N_h) and c_g c_h are sufficient to show that f is in O(n log n).
• Conversely, given f in O(n log n), there are N_f >= 1, c_f such that |f(n)| <= c_f n log n for all n >= N_f. Define g(n) = max(1, n) and h(n) = f(n) / max(1, n); clearly g is in O(n), and we can also see that for n >= N_f we have |h(n)| <= c_f n log n / max(1, n) where the bound on the right hand side is equal to c_f log n because n >= 1, so N_f, c_f are sufficient to show that h is in O(log n). Since we have f(n) = g(n) h(n), it follows that f is in O(n) * O(log n) as we defined it.

The choice of N_f >= 1 and g(n) = max(1, n) is to avoid dividing by zero when n is zero.

actually, the definition of Big-o is not commutative, lets see the example:

let f be defined as f(n) = n

f(n) = O(n^2) & f(n) = O(n^3), but O(n^2) != O(n^3)

that's because using equal sign = is not accurately define here we should say f(n) is O(g).

anyway being a little inaccurate, here is the definition of Big-O grabbed by sipser:

Say that f (n) = O(g(n))
if positive integers c and n 0 exist such that for every integer n ≥ n0, f (n) ≤ c g(n).
When f (n) = O(g(n)), we say that g(n) is an upper bound for When f (n) = O(g(n)), we say that g(n) is an upper bound for f (n), or more precisely, that g(n) is an asymptotic upper bound for f (n), to emphasize that we are suppressing constant factors.

So for proving what you state you must first define what * means in your equation. and show for every function which is O(n log n), it is also O(n) * O(log n) and vice-versa.

but being inaccurate again and define * as symbolic polynomial multiplication we have the following for some constant positive c and d.

O(n log n) = O(cn log n) = O(log n ^ (cn)) = O(d log n^(cn)) = O(log (n^cn) ^ d) = O(log n^cdn) ~= log n ^ cdn ~= cdn * log n

= O(n) * O(log n) = O(cn) * O(d log n) = O(cn) * O(log n^d) ~= cn * (log n^d) ~= cn * d*logn ~= cdn * log n