CODEWITHSUNDEEP
javacomplexity-theorytreeset
Betlista
Betlista

Reputation: 10549

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

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.

Upvotes: 12

Views: 3768

Answers (1)

Mikhail Vladimirov
Mikhail Vladimirov

Reputation: 13890

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

Upvotes: 16

Related Questions