11

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.

Betlista
  • 10,327
  • 13
  • 69
  • 110

1 Answers1

15

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;
}
Mikhail Vladimirov
  • 13,572
  • 1
  • 38
  • 40
  • Could you please clarify one thing? Method iterator() will actually return tree's Iterator<> which is O(log N). It will touch only portion of tree by criteria (fromStart()/toEnd()). As I understood, when headSet() is being created it doesn't actually create a set of elements. It just creates a wrapper with criteria. Am I wrong? Thanks. – Nikolay Antipov Nov 26 '15 at 13:48
  • I returned to that question after some time... You are correct - it creates just a wrapper, but iteration (`while` loop) is still O(K) for subset of size K. – Betlista Mar 09 '17 at 09:48