[erlang-questions] gb_trees and dict performance

[Vladimir Ralev]

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. So if
you insert an element in a dict or tree instead of O(1) or O(logN) it
would be O(N) complexity in both time and memory. I realize there are
some shortcuts done internally to reuse the memory but I imagine that
is not always possible.

Two questions:

1. Can someone comment on the average complexity, is it in line with
what the collections in other languages offer?

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?