What is the complexity of the insert (put) algorithm in TreeMap?

In Java, the TreeMap class is implemented based on a red-black tree — a balanced binary search tree.

The complexity of the insert operation (put) in TreeMap is O(log n), where n is the number of elements in the map.

This is because, to insert, you need to:

• Find the position for the new key (search in the tree) — O(log n).
• Insert the element and, if necessary, perform tree balancing (rotations and recoloring) — also O(log n) in the worst case.

Thus, insertion in TreeMap is efficient and scalable due to its balanced data structure.