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：

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)