I had an argument with a friend about the following problem:
If you ran binary search on two data sets of unknown lengths (for instance sorted arrays m and n) and had to define the time complexity for the entire function, what would it be? Would it be O(log(m + n)), or O(log(m)) if m > n and O(log(n)) if n > m?
Its either O(log(m)) if m>n or O(log(n)) if n>m because in general for n elements we have O(log(n)). the worst case means at the worst till what element it may go to that will be the nth or the mth element if either of the two is maximum. note this is for synchronous meaning parallel if asynchronous it will be log(m)+log(n)
You are running two independent searches on two independent arrays, not one search on one large array.
Thus, the complexity of the two operations is just added together - O(log(n)) + O(log(m)). As you mentioned, if n>m, the
m complexity is negligible and you'd be left with O(log(n)), and vice-versa.