Check if 2 arrays contain the same element

Actually, 1 byte

∩

Try it online!

This is merely the set intersection built-in. The resultant value is the intersection of the two sets - a non-empty list (which is a truthy value) if there is an intersection, and an empty list (which is a falsey value) otherwise.

Complexity

According to the Python Wiki, set intersection has a worst-case time complexity of O(N*M) (where N and M are the lengths of the two sets). However, the time complexity is only that bad when the two sets contain distinct objects that all have the same hash value (for example, {"some string"} & {hash("some string")}). Since the set elements are only integers in this case (and no two integers hash to the same value unless they are equal), the actual worst-case complexity is O(min(N, M)) (linear in the length of the smaller of the two sets). The construction of each set is O(N) (linear in the number of elements), so the overall complexity is O(max(N, M)) (the complexity is dominated by the construction of the larger set).

TSQL, 40 37 36 bytes

SQL doesn't have arrays, it is using tables instead

Returns -1 for true or 0 for false

DECLARE @ table(a INT)
DECLARE @2 table(b INT)

INSERT @ values(1),(2),(3),(4),(-5)
INSERT @2 values(5),(6),(7),(8)

SELECT~-sign(min(abs(a-b)))FROM @,@2

Try it out

Perl, 25+1 = 26 bytes in collaboration with Dada

print 2<($a{$_}|=$.)for@F

Run with -a (1 byte penalty).

An improved version of the program below (which is kept around to see the history of the solution, and to show the solution I found by myself; it also has more explanation). The -a option reads space-separated arrays as the input, storing them in @F. We use the %a dictionary (accessed as $a{$_}) to store a bitmask of which input arrays the input is in, and print 1 every time we see an element in both arrays, i.e. a value higher than 2 inside the resulting bitmask (fortunately, a failing comparison returns the null string, so the print does nothing). We can't use say because a newline is truthy in Perl. Performance is asymptotically the same as the older version of the program (but faster in terms of constant factors).

Perl, 44+1 = 45 bytes

$a{"+$_"}|=$.for split}{$_={reverse%a}->{3}

Run with -p (1 byte penalty). Input one array per line, separating the elements by spaces.

This works via creating a hash table %a that stores a bitmask of the input arrays that a value has been seen in. If it's been seen in both the array on line 1 and on line 2, the bitmask will therefore store the value 3. Reversing the hash and seeing if 3 has a corresponding key lets us know if there are any values in common.

The complexity of this algorithm is O(n) if you consider hash creation to be constant time (it is, if you have bounded integers, like Perl does). If using bignum integers (which could be input into this program, as it leaves the input as a string), the complexity of the algorithm itself would nominally be O(n log n) for each hash creation, and O(n) for the hash reversal, which adds up to O(n log n). However, Perl's hashing algorithm suffers from potential O(n²) performance with maliciously selected input; the algorithm is randomized, though, to make it impossible to determine what that input is (and it's possible that it can't be triggered simply with integers), so it's debatable what complexity class it "morally" counts with. Luckily, this doesn't matter in the case where there's only finitely many possible distinct elements in the array.

This code will work for input other than integers, but it won't work for more than two arrays (because the 3 is hardcoded and because input on the third line wouldn't bitmask correctly, as it isn't a power of 2). Rather annoyingly, the code naturally returns one of the duplicate elements, which is truthy in almost all cases, but "0" is falsey in Perl and a valid duplicate element in the array. As such, I had to waste three bytes prepending a + to the output, which is the cheapest way I found to give a truthy output in the edge case of the arrays overlapping at 0. If I'm allowed to use notions of truthy and falsey from a language other than Perl (in which any nonempty string is truthy), you can change "+$_" to $_ to save three bytes.