Big-O summary for Java Collections Framework implementations?

Question

I may be teaching a "Java crash-course" soon. While it is probably safe to assume that the audience members will know Big-O notation, it is probably not safe to assume that they will know what the order of the various operations on various collection implementations is.

I could take time to generate a summary matrix myself, but if it's already out there in the public domain somewhere, I'd sure like to reuse it (with proper credit, of course.)

Anyone have any pointers?

Answer 1

Here is a link I found to be useful when discussion some very common Java objects and how much their operations cost using Big-O notation.

http://objectissues.blogspot.com/2006/11/big-o-notation-and-java-constant-time.html

Answer 2

Though not in the public domain, the excellent Java Generics and Collections by Maurice Naftalin and Philip Wadler lists runtime information overviews in its chapters on the different collection classes.

Answer 3

The Javadocs from Sun for each collection class will generally tell you exactly what you want. HashMap, for example:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

TreeMap:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

TreeSet:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

(emphasis mine)

Answer 4

The book Java Generics and Collections has this information.

The bottom of the javadoc for the java.util package contains some good links:

• Collections Overview has a nice summary table.
• Annotated Outline lists all of the implementations on one page.

Answer 5

The guy above gave comparison for HashMap / HashSet vs. TreeMap / TreeSet.

I will talk about ArrayList vs. LinkedList:

ArrayList:

• O(1) get()
• amortized O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(n) to shift all the following elements

LinkedList:

• O(n) get()
• O(1) add()
• if you insert or delete an element in the middle using ListIterator.add() or Iterator.remove(), it will be O(1)

Answer 6

Java in a Nutshell, Fifth Edition from O'Reilly also contains a run down of the best, worst, and average times of typical collections.

Answer 7

Just for benefit of others this link has a section section covering almost all collections and their Big O Notation list for most of the important methods.

BigONotationJavaCollections

Hope this help

Answer 8

I found this cheat sheet on the Collections framework to be pretty useful - contains Big O summary information for all implementations.

http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Source