Big 'O' notation and Java Constant time performance

Big 'O' notation and Java Constant time performance

Collection Constant time performance, in a line is "The same amount of time taken for a certain operation(method) regardless of the number of elements in the collection"

Big 'O' notation

The Big O notation is used to indicate the time taken by algorithms to run :-

For example:-
(N is the number of elements)

O(N):- The time taken is linerarly dependent to the number of elements.

O(log N):- The time taken is logarithmic to the number of elements.

O(1):- The time taken is constant time, regardless of the number of elements.

Please read here to find out about the big O notation:-

http://en.wikipedia.org/wiki/Big_O_notation

In java collections

Sets

1) The HashSet offers constant time performance for basic operations (add, remove, contains and size).

2) The TreeSet provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

3) Like HashSet, the LinkedHashSet provides constant-time performance for the basic operations (add, contains and remove)

Lists

4) The ArrayList offers constant time performance in the size, isEmpty, get, set, iterator, and listIterator operations. The add operation runs in linear time. All of the other operations run in linear time (roughly speaking).

Maps

5) The HashMap provides constant-time performance for the basic operations (get and put).

6) The TreeMap provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

7) Like HashMap, the LinkedHashMap provides constant-time performance for the basic operations (add, contains and remove), assuming the the hash function disperses elements properly among the buckets.

If you need a List you could use the ArrayList.

If you need a Set use the HashSet or for a sorted set use the TreeSet or an insertion ordered set use the LinkedHashSet.

If you need a Map use the HashMap or for a key sorted map use the TreeMap or a key insertion ordered map use the LinkedHashMap.

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