[erlang-questions] Ets bag complexity
Mon Dec 10 15:12:10 CET 2012
Gleb Peregud wrote:
> Hello list
> As far as I can understand from paper  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
> - 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.
More information about the erlang-questions