The time complexity of the contains() method in a List is O(n).
This is because the list must iterate through each element sequentially to check whether the target element exists. In the worst case, it may have to check all elements, making it a linear search operation.
Example:
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
boolean exists = list.contains(2); // O(n) time complexity
Optimization
If your use case frequently involves searching for elements, it’s more efficient to use a data structure that offers faster lookups, such as:
HashSet or HashMap, which provide O(1) average-time complexity for contains() or get() operations.
Example using HashSet:
Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);
boolean exists = set.contains(2); // O(1) average time
Summary:
-
List.contains()→ O(n) (linear search) -
HashSet.contains()/HashMap.get()→ O(1) on average (constant time)