I am finding an algorithm for a problem where I have two sets A and B of points with n and m points. I have two algorithms for the sets with complexity O(n log n) and O(m) and I am now wondering whether the complexity for the both algorithms combined is O(n log n) or O(m).

Basically, I am wondering whether there is some relation between m and n which would result in O(m).

CodePudding user response：

If m and n are truly independent of one another and neither quantity influences the other, then the runtime of running an O(n log n)-time algorithm and then an O(m)-time algorithm is will be O(n log n m). Neither term dominates the other - if n gets huge compared to m then the n log n part dominates, and if m is huge relative to n then the m term dominates.

This gets more complicated if you know how m and n relate to one another in some way. Many graph algorithms, for example, use m to denote the number of edges and n to denote the number of nodes. In those cases, you can sometimes simplify these expressions, but sometimes cannot. For example, the cost of implementing Dijkstra’s algorithm with a Fibonacci heap is O(m n log n), the same as what we have above.

CodePudding user response：

Size of your input is x: = m n.

Complexity of a combined (if both are performed at most a constant number of times in the combined algorithm) algorithm is:
O(n log n) O(m) = O(x log x) O(x) = O(x log x).

CodePudding user response：

Yes if m ~ n^n, then O(logm) = O(nlogn).

There is a log formula:

log(b^c) = c*log(b)

EDIT:

For both the algos combined the Big O is always the one that is larger because we are concerned about the asymptotic upper bound. So it will depend on value of n and m. Eg: While n^n < m, the complexity is Olog(m), after that it becomes O(nlog(n)). For Big-O notation we are only concerned about the larger values, so if n^n >>>> m then it is O(nlog(n)), else if m >>>> n^n then it is O(logm)