What is complexity of size() for TreeSet portion v

问题:

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.

回答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;
}