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

2 Answers

2 Answers

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

Add your own answers!

Related Questions

JS get random value from array and update array

2  Asked on December 27, 2020 by nicolas-schmit


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


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


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


Automate and looping through batch script

2  Asked on December 25, 2020 by nck_505


issue connecting Heroku PHP stack to Redis using Predis

0  Asked on December 25, 2020 by rob-edlin


Ask a Question

Get help from others!

© 2021 All rights reserved.