4

I am trying to figure out what are the complexities (using the big-o notation) of operations on Java basic collections. Similarly as in this question for C++ language.

Here is what I have, using the common sense:

Lists

ArrayList

  • add(E e) O(1)
  • add(int index, E e) O(n)
  • set(int index, E element O(1)
  • get(int index) O(1)
  • remove(E e) remove(int index) O(n)
  • contains(E e) O(n)
  • list concatenation (addAll) O(n)

LinkedList

  • add(E e) O(1)
  • add(int index, E e) O(n)
  • set(int index, E element O(n)
  • get(int index) O(n)
  • remove(E e) remove(int index) O(n)
  • contains(E e) O(n)
  • list concatenation (addAll) O(1)

Sets

HashSet and LinkedHashSet

  • add(E e) O(1)
  • remove(E e) O(1)
  • contains(E e) O(1)
  • find/get an element using iterator O(n)

TreeSet

  • add(E e) O(log n)
  • remove(E e) O(log n)
  • contains(E e) O(log n)
  • addAll O(n log n)
  • find an element using iterator O(n) or perhaps O(log n) when implementing the binary search

Maps

HashMap and LinkedHashMap

  • put(K key, V value) O(1)
  • get(K key) O(1)
  • remove(E e) O(1)
  • containsKey(Object key) O(1)
  • containsValue(Object value) O(n)
  • putAll O(n)
  • find/get an element using iterator O(n) or perhaps O(log n) same as in TreeSet

TreeMap

  • put(K key, V value) O(log n)
  • get(K key) O(log n)
  • remove(E e) O(log n)
  • containsKey(Object key) O(log n)
  • containsValue(Object value) O(n)
  • putAll O(n log n)
  • find/get an element using iterator O(n)

NOTE: Collections based on hashing assume well designed hash function to be in O(1) otherwise it is in O(n)

The Question: Is this correct?

Community
  • 1
  • 1
Jiri Kremser
  • 12,471
  • 7
  • 45
  • 72
  • 3
    `ArrayList.Add(E e)` have an _amortized_ constant time. – MAV Aug 19 '13 at 23:41
  • @MAV Isn't that true for a lot of `add`s? (I mean, more of the ones mentioned above, not just ArrayList) – keyser Aug 19 '13 at 23:44
  • It's hard to say that all or none of these are correct, especially considering that functions like `remove()` would depend on how they were implemented. I think this question is way to broad. – BlackHatSamurai Aug 19 '13 at 23:45
  • @Kᴇʏsᴇʀ Most likely. I haven't read the documentation for all of the mentioned collections. – MAV Aug 19 '13 at 23:47
  • @MAC Right, it is amortized constant time. Let's just assume it was created with maximum initial capacity. – Jiri Kremser Aug 19 '13 at 23:50
  • 1
    -1 This question bothers me, because it basically amounts to "I couldn't be bothered to read the docs, can someone read my version of them and tell me if I happened to be right?" I thought for a while about this downvote, but in the end the total lack of any research pushed me over. If the question had been about a specific collection, citing the doc and not being sure of an aspect about it, that'd be one thing; but this question can be answered by just copy-pasting from the javadocs (as evidenced by the fact that it was), which makes it a pretty poorly researched question. – yshavit Aug 20 '13 at 01:21
  • @yshavit So you suggest creating 6 different questions? The added value here is having everything in the one question. I know that "am I right" kind of questions are bad for SO, but I didn't know how to put it differently. Frankly, 50% Java questions on SO can be answered by copy&pasting the jdoc. I haven't noticed the complexities are mentioned in the jdoc (they are not mentioned in the method section, but on the very top in the long description). – Jiri Kremser Aug 20 '13 at 09:42

1 Answers1

3

Your best source of knowledge about this would be the documentation. Here is what I could find with a quick search or two.

Lists

ArrayList

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

LinkedList

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

From what I remember about doubly-linked lists, I would say your "common sense assumption" is correct.

Sets

HashSet

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets).

LinkedHashSet

Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashSet, due to the added expense of maintaining the linked list, with one exception: Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity.

TreeSet

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

Maps

HashMap

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).

LinkedHashMap

Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap,...

TreeMap

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

If some of the methods are not mentioned, try to look up that specific method. If the running time is not mentioned anywhere in the documentation, it might be implementation dependent.

Community
  • 1
  • 1
MAV
  • 7,260
  • 4
  • 30
  • 47