Eu estou querendo saber qual é a complexidade do temposize() para exibição de parte do TreeSet.

Vamos dizer que estou adicionando números aleatórios para definir (e não me importo com duplicidades):

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

e agora eu estou enlouquecendo o que é complexidade parasize() chama como:

    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 complexidade detree.headSet( t ), tree.tailSet( f ) etree.subSet( f, t ) são O (lg N),set.size() é O (1), mas e quanto asize() métodos acima? Eu tenho um sentimento tão ruim que é O (K), onde K é o tamanho do subconjunto selecionado.

Talvez se houver alguma solução para encontrar o índice de algum elemento no conjunto seria suficiente, porque se eu conseguirti = indexOf(f), digamos O (lg N) do que exatamente o que eu preciso.