mason
BAN USERIf a and b are within the same order of magnitude in size, then O(a.length * log(b.length)) is not an improvement over O(a.length + b.length). But if you know that a << b, then yeah, this is probably better. For instance, a.length = 5, b.length=32, a.length+b.length = 37, and a.length * log(b.length) = 25. But suppose both are 32. Then a.length+b.length = 64, but a.length * log(b.length) = 160. Like a lot of optimizations on this problem, it comes down to knowing something about your data. In this case, a quick test could tell you if this is likely to speed up your running time.
- mason February 25, 2014Take the smaller of the two arrays. Do a binary search to find whether there exists an element in the longer array s.t. a[0]+b[x] = N. That search just takes log(b) time. Now, walk backwards along the longer array from that point, looking for elements that satisfy a[i] + b[j] = N. Each time you either find an element s.t. a[i] + b[j] <= N move forward once in a and re-test. Continue going forward in a until a[i] + b[j] >= N. Then resume going backward through b.
I think that's the optimal algorithm, but yeah, it's going to run in O(a+b). I mean, you could get cute about it and if you know N is odd, you could only test a[i] with b[j] when one is odd and the other is even, or if N is even, only test a[i] and b[j] when both are odd or both are even. Testing for evenness means only looking at the least order bit, which might be faster than actually adding two numbers, especially if they're very large. But in the worst case, all pairs between a and b are potentially valid by this test, and all you've done is add a small piece of work to every step. So, perhaps there are optimizations possible depending on what you know about your data, but for the general case, I think O(a+b) is as good as you're liable to get.
Michael J Keating, if a function's running time is in the order of a.len + a.len * log(b.len), in big-Oh notation, we typically just call it O(a.len * log(b.len)). Since we're considering only the asymptotic running times, the linear term in a.len becomes negligible for higher values of a.len and b.len.
- mason February 25, 2014