What is the big O/time complexity for Java Collections disjoint() Method for two hash sets of integers?
Would appreciate any help, really stumped as I'm not sure if it's O(1) or O(n).
I know the hash set contains is an O(1) operation , but I'm not sure if the disjoint operation loops through all the elements of set 1 and checks if set 2 contains any of these elements.
It's O(n).
Let's assume the set query is O(1). You need to iterate through one of the sets, and make queries in the other set to see if it contains the items.
Therefore, the set iterations take O(n) time at least (you can choose to iterate the set with a smaller size. That's what they did in the source code).
In total, time complexity is O(n).