Big-O complexity of multiple variables with different functions

Question

I am trying to figure out what is the total Big-O complexity of a problem with multiple variables and different mathematical functions.

The two big steps in the problem takes O(n*m) and O(n*logn). Both n and m are independent and can be very big or very small.

What is the correct complexity? Is it O(n*m)? O(n*logn)? Or O(n*m+n*logn)?

score 0 · Accepted Answer · answered Aug 22 '16 at 22:46

0

Assuming the two big steps happen one after the other (not in parallel), the best we can say is that it takes $O(nm + n\log(n))$ time to complete. If you knew more information of how $n$ and $m$ relate to eachother then you could simplify more.

answered Aug 22 '16 at 22:46

nullUser

27,877

They don't relate to each other at all and are independent. – Tom Forde Aug 22 '16 at 22:47
And yes they happen one after the other, not in parallel. – Tom Forde Aug 22 '16 at 22:47
Since they are independent, you cannot simplify the answer beyond what I wrote. – nullUser Aug 22 '16 at 22:48
Also we must be assuming these are the ONLY two steps, or all other steps take constant time. Of course if there are three steps and the third one takes $O(n^2m^2)$ the answer would be wrong. – nullUser Aug 22 '16 at 22:49

Big-O complexity of multiple variables with different functions

1 Answers1