[erlang-questions] Ets bag complexity

[Sverker Eriksson]

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