CODEWITHSUNDEEP
javatreemap
mac
mac

Reputation: 85

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?

Upvotes: 6

Views: 3518

Answers (1)

Eran
Eran

Reputation: 393956

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.

Upvotes: 6

Related Questions