Complexity of treeset's subset method?

Question

I am looking for time complexity of subset method of treeset. Is it O(n) where n is the number of items in the navigation set ?

Answer 1

The subSet() method of TreeSet internally calls subMap() method of TreeMap. TreeMap in Java is implemented using Red-Black tree. The subMap() method return new object of SubMap class, which is an internal class(nested class) in TreeMap. The constructor of SubMap class only store the first and last key of the subMap as implemented below:

SubMap(Object minKey, Object maxKey)
{
  if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
    throw new IllegalArgumentException("fromKey > toKey");
  this.minKey = minKey;
  this.maxKey = maxKey;
}

Most operation takes same time as TreeMap, except the size() method. The size() method of SubMap class is implemented as below:

public int size()
{
  //Returns node >= minKey(i.e. first node in subSet). Takes O(logN) time.
  Node node = lowestGreaterThan(minKey, true);
  //Returns node >= maxKey(i.e. first node in subSet). Takes O(logN) time.
  Node max = lowestGreaterThan(maxKey, false);
  int count = 0;
  while (node != max)
    {
      count++;
      //In worst case, successor takes logN time
      node = successor(node);
    }
  return count;
}

The lowestGreaterThan() method takes O(logN) to find the key in subset. The successor() method takes O(logN), which is proportional to height in Red-Black tree, to find next successor. And to find the size of NavigableSet return by subSet, we need to traverse through each node in the subSet. Hence, the total complexity of function SubMap.size():- O(logN)+O(logN)+O(MlogN) ~ O(MlogN), where M is size of subset.