Crash - 4 months ago 21

Java Question

I am brushing up algorithms and data structures and have a few questions as well as statements I would like you to check.

**ArrayList** - O(1) (size, get, set, ...), O(n) - add operation.

**LinkedList** - all operation O(1) (including add() ), except for retrieving n-th element which is O(n). I assume size() operation runs in O(1) as well, right?

**TreeSet** - all operations O(lg(N)). size() operation takes O(lg(n)), right?

**HashSet** - all operations O(1) if proper hash function is applied.

**HashMap** - all operations O(1), anologous to HashSet.

Any further explanations are highly welcome. Thank you in advance.

Answer

`ArrayList.add()`

is *amortized* O(1). If the operation doesn't require a resize, it's O(1). If it *does* require a resize, it's O(n), but the size is then increased such that the next resize won't occur for a while.

From the Javadoc:

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). The constant factor is low compared to that for the LinkedList implementation.

The documentation is generally pretty good for Java collections, in terms of performance analysis.

The O(1) for hash algorithms isn't a matter of just applying a "proper" hash function - even with a very good hash function, you could still happen to get hash collisions. The *usual* complexity is O(1), but of course it can be O(n) if *all* the hashes happen to collide.