[erlang-questions] gb_trees and dict performance

[Richard A. O'Keefe]

On 10/12/2015, at 2:00 am, Vladimir Ralev <vladimir.ralev@REDACTED> wrote:

> Hi all,
> 
> I am curious about the O-complexity of the operations in these data
> structures in Erlang. It would seem to me that because of immutability
> adding elements in those structures would often require a duplication
> of the data structure and copying is an O(N) operation itself.

Because of immutability, adding (or deleting) elements
in those structures nearly always requires duplicating
***PART*** of the data structures.  But since they are
trees, ONLY part.

The amount of new space allocated (in pretty much any
functional language) is going to be roughly proportional
to the length of the path that the call traverses.  This
means O(log N) time and O(log N space), even taking
(local) rebalancing into account.
> 
> 2. If you have a job interview and are asked what is the complexity of
> dict:store() and gb_trees:enter() what would you say?

Me, I'd hire the guy who said "I'd expect it to be logarithmic,
but if it mattered I would make sure to check the documentation,
and if it REALLY mattered I would do my own benchmarks."