What is complexity of size() for TreeSet portion view in Java

Question

I'm wondering what is the time complexity of size() for portion view of TreeSet.

Let say I'm adding random numbers to set (and I do not care about duplicities):

    final TreeSet<Integer> tree = new TreeSet<Integer>();
    final Random r = new Random();
    final int N = 1000;
    for ( int i = 0; i < N; i++ ) {
        tree.add( r.nextInt() );
    }

and now I'm wodering what is complexity for size() calls as:

    final int M = 100;
    for ( int i = 0; i < M; i++ ) {
        final int f = r.nextInt();
        final int t = r.nextInt();
        System.out.println( tree.headSet( t ).size() );
        System.out.println( tree.tailSet( f ).size() );
        if ( f > t ) {
            System.out.println( tree.subSet( t, f ).size() );
        } else {
            System.out.println( tree.subSet( f, t ).size() );
        }
    }

AFAIK complexity of tree.headSet( t ), tree.tailSet( f ) and tree.subSet( f, t ) are O(lg N), set.size() is O(1), but what about size() methods above? I have such a bad feeling that it's O(K) where K is size of selected subset.

Maybe if there is some workaround to find index of some element in set it would be enough, because if I can get ti = indexOf(f), in let say O(lg N) than it is exactly what I need.

Answer 1

Looks like complexity of size () is O(N), because it may call TreeMap.NavigableSubMap.EntrySetView.size () which is implemented like this (Oracle JDK 1.7.0_13):

public int size() {
    if (fromStart && toEnd)
        return m.size();
    if (size == -1 || sizeModCount != m.modCount) {
        sizeModCount = m.modCount;
        size = 0;
        Iterator i = iterator();
        while (i.hasNext()) {
            size++;
            i.next();
        }
    }
    return size;
}