big o - What is asymptotic complexity for CRUD operations on basic Java containers -

i trying figure out complexities (using big-o notation) of operations on java basic collections. in question c++ language.

here have, using 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 , linkedhashset

• add(e e) o(1)
• remove(e e) o(1)
• contains(e e) o(1)
• find/get 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 element using iterator o(n) or perhaps o(log n) when implementing binary search

---

maps

hashmap , 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 element using iterator o(n) or perhaps o(log n) same 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 element using iterator o(n)

note: collections based on hashing assume designed hash function in o(1) otherwise in o(n)

the question: correct?

your best source of knowledge documentation. here find quick search or two.

lists

arraylist

the size, isempty, get, set, iterator, , listiterator operations run in constant time. add operation runs in amortized constant time, is, adding n elements requires o(n) time. of other operations run in linear time (roughly speaking).

linkedlist

all of operations perform expected doubly-linked list. operations index list traverse list beginning or end, whichever closer specified index.

from remember doubly-linked lists, "common sense assumption" correct.

sets

hashset

this class offers constant time performance basic operations (add, remove, contains , size), assuming hash function disperses elements among buckets. iterating on set requires time proportional sum of hashset instance's size (the number of elements) plus "capacity" of backing hashmap instance (the number of buckets).

linkedhashset

like hashset, provides constant-time performance basic operations (add, contains , remove), assuming hash function disperses elements among buckets. performance below of hashset, due added expense of maintaining linked list, 1 exception: iteration on linkedhashset requires time proportional size of set, regardless of capacity. iteration on hashset more expensive, requiring time proportional capacity.

treeset

this implementation provides guaranteed log(n) time cost basic operations (add, remove , contains).

maps

hashmap

this implementation provides constant-time performance basic operations (get , put), assuming hash function disperses elements among buckets. iteration on collection views requires time proportional "capacity" of hashmap instance (the number of buckets) plus size (the number of key-value mappings).

linkedhashmap

like hashmap, provides constant-time performance basic operations (add, contains , remove), assuming hash function disperses elements among buckets. performance below of hashmap,...

treemap

this implementation provides guaranteed log(n) time cost containskey, get, put , remove operations.

if of methods not mentioned, try specific method. if running time not mentioned anywhere in documentation, might implementation dependent.