Ich frage mich, was ist die zeitliche Komplexität vonsize() für Teilansicht von TreeSet.

Angenommen, ich füge Zufallszahlen zum Festlegen hinzu (und Duplizitäten interessieren mich nicht):

    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() );
    }

und jetzt frage ich mich, wofür Komplexität istsize() ruft an als:

    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 Komplexität vontree.headSet( t ), tree.tailSet( f ) undtree.subSet( f, t ) sind O (lg N),set.size() ist O (1), aber was istsize() Methoden oben? Ich habe so ein schlechtes Gefühl, dass es O (K) ist, wo K die Größe der ausgewählten Teilmenge ist.

Vielleicht reicht es aus, wenn es eine Problemumgehung gibt, um den Index eines Elements in der Menge zu finden, denn wenn ich es bekommen kannti = indexOf(f), sagen wir mal O (lg N), dann ist es genau das, was ich brauche.