[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