What is the correct Big O Notation for this problem?

475 views big-o

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?

answered question

4 Answers


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)

posted this

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.

posted this

This would be O(log(mn)): this is true whichever of the two is the greatest. Note that logarithms have this invariance:

  log(mn) = log(m) + log(n)

posted this

There is a Google Analytics Debugger Chrome extension, that allows you to see everything going out from that browser.

posted this

Have an answer?


Please login first before posting an answer.