[erlang-questions] Ets bag complexity
Mon Dec 10 15:24:39 CET 2012
>> - insert operations are amortized O(1) (sometimes resizing of arrays is
> insert in bag is also O(1+K) as we have to make sure that we do not insert
>> - 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