I feel O(n+m) is the correct bound. In the worst case scenario that both arrays are identical, then 2*m numbers must be outputted (is that a word?). So O(m+n) is worst case bound.
However, it will interesting if say you know there are a maximum of k common numbers between the two arrays. What would a good algorithm be then? What would be it's complexity? I'm sorta thinking aloud on this one... so the solution could be quite trivial.
