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

I came across a problem where O(nm) is being ran against O(n log n) and they say that one is better but it’s not so obvious to me.

O(n log n) is better than O (n^2), but what about compared to O(n*m) with m being a non-constant?

Stack Overflow Asked by krankykong on November 15, 2021

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.

Answered by Yves Daoust on November 15, 2021

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)

Answered by SomoKRoceS on November 15, 2021

## Related Questions

### JS get random value from array and update array

2  Asked on December 27, 2020 by nicolas-schmit

### Change multiple column names in pandas dataframe (not all colmn names) at the same time using index numbers

2  Asked on December 27, 2020 by mizz-h

### Caught and declared exception in Java?

1  Asked on December 26, 2020 by hrvoje-t

### IEnumerable and Recursion using yield return

8  Asked on December 26, 2020 by jamie-dixon

### How to parse CSV with node.js?

2  Asked on December 26, 2020 by idarosa

### Why this program with for loop give zero when y>5 and x=2

2  Asked on December 26, 2020 by vms

### Null pointer exception. How my connection object is pointing to null

2  Asked on December 26, 2020 by monisha-ravi

### What is the best way to append custom message to the output when pytest.raises fails?

1  Asked on December 26, 2020 by roman-ponomaryov

### What is wrong in this sorting array skipping some elements?

2  Asked on December 26, 2020 by eymerich

### How do I make contents in HTML by using css

0  Asked on December 26, 2020 by jaeseo-lee

### How to show Toaster after logout

2  Asked on December 26, 2020

### How to write to a csv within a pandas UDF in pyspark?

0  Asked on December 26, 2020 by codemaster2020

### How to add a support for this custom field to be saved outside of Woocommerce product form

0  Asked on December 26, 2020 by marko-i

### Keycloak permission to restrict account based resources

0  Asked on December 26, 2020 by james-lin

### CSS flex, full height sidebar inside a modal?

1  Asked on December 25, 2020 by ddulla

### Cant loop through List and display in DataTable

1  Asked on December 25, 2020 by finchy70

### How to fix Laravel Illegal mix of collations error?

1  Asked on December 25, 2020 by vince

### Automate and looping through batch script

2  Asked on December 25, 2020 by nck_505

### Ionic-5 app is closing instead back to previous page on click of hardware back button

2  Asked on December 25, 2020 by outofworld

### issue connecting Heroku PHP stack to Redis using Predis

0  Asked on December 25, 2020 by rob-edlin