Java.Collections.What is the worst case running time of the contains() method for an element that is in an ArrayList?

🔍 contains() in an ArrayList

Just like in LinkedList, the contains() method in ArrayList:

1. Iterates over the internal array from index 0 to size - 1.
2. Uses .equals() to compare each element with the target.

---

⏱️ Worst-case running time: O(n)

• n = number of elements in the list.
• Even though ArrayList allows fast random access, contains() is a linear search.

---

🧠 Why not faster?

Because ArrayList is not sorted and doesn’t use hashing like a HashSet, it has no shortcut. It has to check every element one by one.

---

🧪 Example:

ArrayList<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
// list.contains("c") → O(n) in worst case

Even though ArrayList gives you get(index) in O(1), contains() still loops through all elements.

---

🔁 Comparison: contains() time complexity

Collection Type	contains() Worst Case
ArrayList	❌ O(n)
LinkedList	❌ O(n)
HashSet	✅ O(1)
TreeSet	⚠️ O(log n)