Brewlearn Get the app
🗃️ Collections Framework · Intermediate

Big-O of collection operations in Java

Choosing the right collection by access pattern.

🧩 The mysteryTwo programs do the same job on 100,000 items. One finishes in milliseconds, the other takes minutes. The only difference: which collection they picked.

Big-O: how cost grows

Big-O describes how work grows as n grows. O(1): same cost at any size (open locker #7). O(log n): halve the search each step (dictionary lookup). O(n): look at everything (scan a list). O(n²): everything, for each thing.

The cheat sheet

Arrays jump to an index. Hash tables jump to a bucket. Balanced trees halve the search. Linked nodes walk. Deques keep both ends cheap.

ArrayList   get O(1)  contains O(n)
            add at end amortized O(1)
LinkedList  get(i) O(n)
HashSet/Map add/contains/get O(1) avg
TreeSet/Map O(log n), sorted + ranges
ArrayDeque  add/remove at ends O(1)
🤔 Think first

Seen it before?

You get 100,000 IDs and must check each one against all the IDs you've seen so far. ArrayList or HashSet?

Think about it, then reveal the answer

HashSet. contains on a list scans every element: O(n) per check, O(n²) total. HashSet jumps to a bucket by hash: O(1) average per check, O(n) total. At this size, that's the difference between minutes and milliseconds.

🔮 Predict it

Emptying a list

A loop calls list.remove(0) on an ArrayList of n elements until it's empty. Total cost?

  1. O(n)
  2. O(n log n)
  3. O(n²)
Show the answer

Each remove(0) shifts every remaining element left: O(n) per call, so n calls cost O(n²). ArrayDeque.pollFirst() would make each removal O(1).

Sorted and ranged? Use a tree

Need "all events between 9:00 and 10:00"? A TreeMap keeps keys sorted, so **subMap(from, to) finds the range in O(log n + k)** for k results. A HashMap would have to scan everything.

TreeMap<LocalTime, String> events = ...;
events.subMap(LocalTime.of(9, 0),
              LocalTime.of(10, 0));

Membership checks in a loop

✗ O(n²)
List<String> seen = new ArrayList<>();
for (String id : ids) {
    if (!seen.contains(id)) seen.add(id);
}

contains hides a loop inside your loop.

✓ O(n)
Set<String> seen = new HashSet<>();
for (String id : ids) {
    seen.add(id);
}

Each add/contains is O(1) on average.

💼 In the real world

Why it matters

Collection choice is a top cause of "works on my laptop, dies in production": tests use 10 items, production uses 10 million. It's also an interview staple: expect "what's the complexity of this?" and "which collection would you use?"

Key takeaways

  1. ArrayList: get O(1), contains O(n), add at end amortized O(1)
  2. HashSet/HashMap: add, contains, get O(1) on average
  3. TreeSet/TreeMap: O(log n) but sorted, with range queries
  4. ArrayDeque: add/remove at either end O(1)

💡 Choose collections like tools: a hammer (ArrayList) is great, but not for every screw.

🤯 Did you know?

Big-O notation is older than computers: mathematician Paul Bachmann introduced it in 1894, and Donald Knuth popularized it in computer science in the 1970s.

Practice questions

You receive 100,000 IDs and must check, for each one, whether you've already seen it. Which collection should store the seen IDs?

  1. ArrayList
  2. HashSet
  3. LinkedList
  4. PriorityQueue
Check your answer

HashSet. HashSet's add and contains are O(1) on average, so the whole job is O(n). With a list, each contains is O(n) and the job becomes O(n²).

You store timestamped events and often ask for 'all events between 9:00 and 10:00'. Which is the best fit?

  1. HashMap<Instant, Event>
  2. TreeMap<Instant, Event>
  3. ArrayDeque<Event>
  4. HashSet<Event>
Check your answer

TreeMap<Instant, Event>. TreeMap keeps keys sorted, so subMap(from, to) returns a range in O(log n + k). A HashMap would need to scan everything.

Next world: Generics! What does the <String> in List<String> actually do, and why does it vanish completely at runtime?