7

I know the time complexity of basic operations such as add, get is O(logn). But I didn't found the detail of lower() and higher(). So, what is the time complexity of lower() and higher() of TreeSet in Java?

Tommy
  • 153
  • 2
  • 5
  • Also see [Computational Complexity of TreeSet methods in Java](http://stackoverflow.com/questions/14379515/computational-complexity-of-treeset-methods-in-java) – Sabir Khan Dec 24 '15 at 04:31

4 Answers4

8

TreeSet is backed by an implementation of NavigableMap called TreeMap. The code ultimately called when computing lower() on TreeSet is lowerEntry() on TreeMap.

/**
 * Returns the entry for the greatest key less than the specified key; if
 * no such entry exists (i.e., the least key in the Tree is greater than
 * the specified key), returns {@code null}.
 */
final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

Looking at this code, it looks like with each iteration of the while loop, every branch either returns or traverse one level of the tree. Since Tree Map should have log(n) levels, the entire method has O(log(n)) complexity.

dolan
  • 1,716
  • 11
  • 22
1

In Java TreeSet and TreeMap is a red-black (balanced) binary search tree(BST). And when you are searching (methods: lower() and higher() are actually searching) over the red-black BST time-complexity is going to be 2 log N.

So the time complexity of both methods is O (log N).

Mikhailov Valentin
  • 1,092
  • 3
  • 16
  • 23
0

It's the same as get(), O(log n).

lower() or higher() does a get(); then it does a get() again to find the next (lower or higher) node. Since constants like 2 drop out of big-O notation, it's just O(log n) again.

markspace
  • 10,621
  • 3
  • 25
  • 39
0

It's not specified in the docs, but the implementation — at least for OpenJDK 8 — is O(log n).

TreeSet uses TreeMap under the hood for its operations (with the set's elements stored as the map's keys), and in particular lower() delegates straight to TreeMap::lowerKey (the m field is typed as NavigableMap, but if you look at the constructors you'll see that it's always TreeMap).

TreeMap::lowerKey, in turn, really comes down to a call to getLowerEntry, which starts at the root and then finds the appropriate entry; this is O(log n) in any binary search tree (such as the red-black tree that TreeMap uses).

TreeSet::higher() uses a similar delegation, and has the same performance characteristics.

yshavit
  • 42,327
  • 7
  • 87
  • 124