Time Complexity of Collection Operations

Time complexity describes how the time an operation takes grows as a collection gets bigger. It is written in Big O notation: O(1) means the time stays the same however many elements there are, O(log n) means it grows very slowly, and O(n) means it grows in step with the number of elements. Knowing these costs is how you choose the right collection, and it is asked in nearly every Java interview. In this lesson, you will find the cost of the main operations for each collection, and see why each is what it is.

Big O in Plain Words

"Amortized O(1)" means usually O(1), with an occasional slow step (like resizing) whose cost, spread over many operations, is still constant on average.

Lists

Sets

Maps

HashMap is O(log n) in the worst case, when many keys collide in one bucket that has turned into a tree.

Queues and Deques

Example: O(1) vs O(n) in Practice

Let's see an example that searches for values in a list and a set of the same size. Times vary between computers, so the output is a sample.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
 
public class ContainsCost {
    public static void main(String[] args) {
        int n = 100_000;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        Set<Integer> set = new HashSet<>(list);
 
        long start = System.nanoTime();
        int found = 0;
        for (int i = 0; i < 10_000; i++) {
            if (list.contains(n - 1 - i)) found++;
        }
        long listMs = (System.nanoTime() - start) / 1_000_000;
 
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            if (set.contains(n - 1 - i)) found++;
        }
        long setMs = (System.nanoTime() - start) / 1_000_000;
 
        System.out.println("found " + found);
        System.out.println("ArrayList.contains x 10,000: " + listMs + " ms");
        System.out.println("HashSet.contains   x 10,000: " + setMs + " ms");
    }
}

found 20000
ArrayList.contains x 10,000: 257 ms
HashSet.contains   x 10,000: 0 ms

Explanation: Each ArrayList.contains scans the list from the start, about 100,000 comparisons for values near the end. HashSet.contains jumps straight to one bucket. With 10,000 searches, the difference is hundreds of times.

Common Mistakes

Calling list.contains inside a loop over another big list. That is O(n x m); use a HashSet for lookups.

Using LinkedList.get(i) in a loop. Each call is O(n), making the loop O(n squared).

Forgetting that containsValue on a map is O(n). Only key lookups are fast.

Interview Corner

Practice

1. Easy: For each of these tasks, name the collection with the best cost: checking whether a username is taken; getting the 500th element; always serving the smallest job first.
2. Harder: Find the common elements of two lists of 100,000 numbers, first with nested contains calls, then with a HashSet. Time both and explain the difference using Big O.

Key Takeaways