Course contentsShow
← Java
Lesson 1138 of 2,87026. Map ImplementationsFree lesson

Performance Characteristics: O(log n) Operations

Understanding TreeMap's guaranteed log-time cost for get, put, containsKey, and remove operations.

Performance Characteristics: O(log n) Operations

You'll learn why TreeMap operations take logarithmic time and what that means for real-world performance.

TreeMap guarantees O(log n) time complexity for its core operations: get(), put(), containsKey(), and remove(). This is a direct consequence of the red-black tree structure underneath.

What Does O(log n) Mean?

When you have n entries in a TreeMap, each operation requires at most log₂(n) steps. Think of searching for a word in a dictionary: you don't read every page sequentially—you repeatedly cut the search space in half. That's logarithmic behavior.

Example scale:

  • 1,000 entries → ~10 comparisons maximum
  • 1,000,000 entries → ~20 comparisons maximum
  • 1,000,000,000 entries → ~30 comparisons maximum

Why TreeMap Is O(log n)

The red-black tree maintains balance, ensuring no path from root to leaf is more than twice as long as any other path. When you search for a key, you traverse from root toward a leaf, making one comparison per level. A balanced tree with n elements has approximately log₂(n) levels.

Each operation (get, put, containsKey, remove) involves navigating this tree by comparing keys, so each takes O(log n) time.

Contrast with HashMap

HashMap offers O(1) average case, which seems better—and usually is for large random access patterns. However, TreeMap's O(log n) is guaranteed, with no worst-case rehashing delays, and you get sorted ordering as a bonus.

Key Takeaway: TreeMap guarantees O(log n) time for get, put, containsKey, and remove operations—predictable performance that scales gracefully, even with millions of entries, making it reliable when you need both sorted keys and consistent operation times.