InsideDarkWeb.com

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 InsideDarkWeb.com. All rights reserved.