CODEWITHSUNDEEP
javaalgorithmdata-structuresavl-treetreeset
user1628340
user1628340

Reputation: 941

Computational Complexity of TreeSet methods in Java

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree?

Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher

Java Doc for method description: http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

For an AVL Tree, there are all O(logn)? Whats the complexity of the above TreeSet Methods?

Upvotes: 30

Views: 30560

Answers (3)

Peter Lawrey
Peter Lawrey

Reputation: 533442

EDIT: It should be clarified that the time order usually refers to the number of comparisons. Some operations have no comparisons, so the time order could be taken from the number of sub-tasks

The code below prints the following in Java 8

O(1) comparisons, however the number of indirections could be O(ln N)
Performing 10,000 first operations -> 0.0 comparisons/operation
Performing 10,000 last operations -> 0.0 comparisons/operation
Performing 10,000 size operations -> 0.0 comparisons/operation
Performing 10,000 isEmpty operations -> 0.0 comparisons/operation
Performing 10,000 comparator operations -> 0.0 comparisons/operation
Performing 10,000 pollFirst operations -> 0.0 comparisons/operation
Performing 10,000 pollLast operations -> 0.0 comparisons/operation
Performing 10,000 headSet operations -> 1.0 comparisons/operation
O(ln N) comparisons
Performing 10,000 add operations -> 12.9 comparisons/operation
Performing 10,000 ceiling operations -> 12.9 comparisons/operation
Performing 10,000 contains operations -> 12.9 comparisons/operation
Performing 10,000 floor operations -> 12.9 comparisons/operation
Performing 10,000 higher operations -> 13.9 comparisons/operation
Performing 10,000 lower operations -> 13.9 comparisons/operation
Performing 10,000 remove operations -> 10.9 comparisons/operation
O(N ln N) comparisons
Performing 10,000 equals operations -> 128853.0 comparisons/operation

the code

public class TreeSetOrderMain {
    public static void main(String[] args) {
        System.out.println("O(1) comparisons, however the number of indirections could be O(ln N)");
        testOrder("first", (s, i) -> s.first());
        testOrder("last", (s, i) -> s.last());
        testOrder("size", (s, i) -> s.size());
        testOrder("isEmpty", (s, i) -> s.isEmpty());
        testOrder("comparator", (s, i) -> s.comparator());
        testOrder("pollFirst", (s, i) -> s.pollFirst());
        testOrder("pollLast", (s, i) -> s.pollLast());
        testOrder("headSet", TreeSet::headSet);

        System.out.println("O(ln N) comparisons");
        testOrder("add", TreeSet::add);
        testOrder("ceiling", TreeSet::ceiling);
        testOrder("contains", TreeSet::contains);
        testOrder("floor", TreeSet::floor);
        testOrder("higher", TreeSet::higher);
        testOrder("lower", TreeSet::lower);
        testOrder("remove", TreeSet::remove);

        System.out.println("O(N ln N) comparisons");
        Set<Long> set = LongStream.range(0, 10_000).mapToObj(i -> i).collect(Collectors.toSet());
        testOrder("equals", (s, i) -> s.equals(set));
    }

    static void testOrder(String desc, BiConsumer<TreeSet<Long>, Long> op) {
        final LongComparator comparator = new LongComparator();
        TreeSet<Long> longs = new TreeSet<>(comparator);
        final int count = 10_000;
        for (long i = 0; i < count; i++)
            longs.add(i);
        comparator.count = 0;
        for (long i = 0; i < count; i++)
            op.accept(longs, i);
        System.out.printf("Performing %,d %s operations -> %.1f comparisons/operation%n",
                count, desc, (double) comparator.count / count);
    }

    static class LongComparator implements Comparator<Long> {
        long count = 0;

        @Override
        public int compare(Long o1, Long o2) {
            count++;
            return Long.compare(o1, o2);
        }
    }
}

Operations which work on a single element are all O(ln n) comparisons except first and last which are O(1) comparisons or O(ln N) node search time.

comparator(), iterator(), clear(), first(), isEMpty(), size(), last(), pollFirst(), pollLast(), headSet() are O(1)

add(), ceiling(), contains(), floor(), higher(), lower(), remove(), subSet(), tailSet() are O(ln N)

clone(), hashCode(), toArray() and toString() are O(n) for operations, but no comaprisons

Upvotes: 50

Xinyi Li
Xinyi Li

Reputation: 1012

At least in the current version of JDK, no special handles are applied on first or last (see source code in openjdk/jdk. The code looks like:

    final Entry<K,V> getLastEntry() {
        Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

It should be O(logN), not an exception.

Upvotes: 1

Ast15
Ast15

Reputation: 81

first(), last(), pollFirst(), pollLast(): O(lgn), not O(1).

Upvotes: 7

Related Questions