Big-O Complexity

Last Updated: 2021-12-15

h is the hash table capacity

List implementations:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Set implementations:

                      add      contains next
HashSet               O(1)     O(1)     O(h/n)
LinkedHashSet         O(1)     O(1)     O(1)
CopyOnWriteArraySet   O(n)     O(n)     O(1)
EnumSet               O(1)     O(1)     O(1)
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Map implementations:

                      get      containsKey next
HashMap               O(1)     O(1)        O(h/n)
LinkedHashMap         O(1)     O(1)        O(1)
IdentityHashMap       O(1)     O(1)        O(h/n)
EnumMap               O(1)     O(1)        O(1)
TreeMap               O(log n) O(log n)    O(log n)
ConcurrentHashMap     O(1)     O(1)        O(h/n)
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Queue implementations:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)