javatreeset

Why is TreeSet.remove's time complexity O(in N)?

A treeset is already sorted... so why isn't the time complexity to remove an object O(Log N) through binary search? Am I missing something?

Solution

  • It is O(log N) according to the JavaDocs for TreeSet:

    This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).