Search code examples
javatreemap

Why treemap takes O(log(n)) time in Get/put

In one of the posts I saw that TreeMap takes O(log(n)) time for get/put. Can someone please answer why it takes O(log(n)), even when it can search directly through get/put using key?

Solution

  • In a TreeMap, the key/value entries are stored in a Red-Black tree, and in order to find if a key is contained in the tree, you have to traverse it from the root, down some path, until reaching the required key or reaching a leaf.

    A tree containing n elements has an O(log n) height, and therefore that's the time it would take to search for a key.