[erlang-questions] Ets bag complexity

[Sverker Eriksson]

Gleb Peregud wrote:
>>> - 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!
>
>   
Also to be clear,  there is no heavy resizing of entire hash array. 
Linear hashing is used which means table grows by splitting and 
rehashing one bucket at a time.

>>> - 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.
>
>   
If the key in match-spec is totally bound, the select implementation 
does a hash lookup and thereby get O(1+K).
Otherwise we get O(N*K) from total table traversal.

/Sverker