[erlang-questions] Ets bag complexity

Gleb Peregud gleber.p@REDACTED
Mon Dec 10 15:24:39 CET 2012

>> - 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.

Good point!

>> - 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.

Yes, in general case. I assumed (and didn't inform you) a specific
case when only a single key matches the select match specification.

More information about the erlang-questions mailing list