Which is better: O(nm) or O(n log n)?

You can't answer for at least three reasons:

• if N and M are independent, there is no relation between log N and M;

• asymptotic complexities depend on the constants in the big-O notation, and even for two O(N) functions you don't know which is "better";

• big-O's are just upper bounds and if they are not tight, the true function can be quite different.

When you examine complexity, you must define your input. When your input is N and you want to compute a program complexity, given N, the result will be a function with N as an argument. It is easy to compare between two different functions with the same input.

However, in your case, you are comparing a function that takes one argument (N) with a function that takes two arguments (N and M), while M is unknown relatively to N. Therefore, you can't really compare between them and get the answer you want.

For example, if M is defined as M=N*C (when C is a constant), you can say that O(N*M)=O(N^2)>O(N*logN). But if M is defined as M=log(log(N))*C, then O(N*M)=O(N*log(log(N)))<O(NlogN).

The key point here is that time complexity calculation always relays on every input, which they must be well defined relatively to the other arguments being compared.

So, the answer to (N*M) ? O(N*logN) depends on the relation between M and N (to be more specific: depends on if M*C<log(N)*K, when C and K are constants)