[erlang-questions] Ets bag complexity

Sverker Eriksson sverker.eriksson@REDACTED
Mon Dec 10 15:12:10 CET 2012

Gleb Peregud wrote:
> Hello list
> As far as I can understand from paper [1] by Scott Lystic Fritchie ETS
> tables of 'bag' type are implemented as a hash table with linear
> arrays of values attached to each key?
> So, are the following statements correct for bag ETSes?
> - lookup and delete operations for key which has K values is of
> average complexity O(1+K)
> - insert operations are amortized O(1) (sometimes resizing of arrays is needed)
insert in bag is also O(1+K) as we have to make sure that we do not 
insert duplicates.

> - select operations are O(N+K) where N is a number of keys, K is
> number of values
I guess you mean O(N*K) if K is average number of values per key. In 
other words traversal of the entire table.

/Sverker, Erlang/OTP

More information about the erlang-questions mailing list