Menu
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?
638
For HashSet, LinkedHashSet, and EnumSet, the add(), remove() and contains() operations cost constant O(1) time thanks to the internal HashMap implementation. Likewise, the TreeSet has O(log(n)) time complexity for the operations listed in the previous group. This is because of the TreeMap implementation.
From TreeSet : This implementation provides guaranteed log(n) time cost for the basic operations ( add , remove and contains ). You are performing a ~log(n) operation n times, hence the complexity is indeed O(n log(n)).
The TreeSet class internally uses a TreeMap to store elements. The elements in a TreeSet are sorted according to their natural ordering. You may also provide a custom Comparator to the TreeSet at the time of creation to let it sort the elements based on the supplied comparator.
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() are O(1)
add(), ceiling(), contains(), floor(), headSet(), higher(), lower(), remove(), subSet(), tailSet() are O(ln N)
clone(), equals(), hashCode(), toArray() and toString() are O(n)
75
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
