Then you actually work with sets, not lists. If it is possible, I suggest storing this data as sets in the first place, then you can compare them with simple: set1 == set2. If you have to use list/iterables, then you can easily convert them to sets:
list1.toSet() == list2.toSet()
But it may be a little more performant if converting only the first one:
list1.toSet().containsAll(list2)
Regarding the time complexity. HashSet has constant time complexity for both inserting and looking for an item. Therefore, converting a list to set is O(N) and looking for N elements should be also O(N). So, converting and searching is O(N+M)where N is the size of the first collection and M is the size of the second collection.
BTW, searching in a list is O(N), so containsAll() should be O(N*M) - much more.