I am currently trying to compile a
Big-O Time Complexity table for the Elixir data structures, but can’t find information for all complexities and am also not 100% sure that I’m getting them right. My goal is to have a comprehensive table like the Big-O Algorithm Complexity Table and maybe put it into a nice cheatsheet poster for future reference. I was able to find bits and pieces in the docs, Elixirforum posts and the Elixir mailing list, but I failed to find a comprehensive overview of all the complexities.
Would you mind helping me to complete and review the following table, please?
# Big-O Time Complexities for Elixir data structures
# Map 
Access: O(log n)
Search: O(log n)
Insertion: O(n) for < 32 elements, O(log n) for >= 32 elements 
Deletion: O(n) for < 32 elements, O(log n) for >= 32 elements 
- 'With fewer than 32 elements, a Map is a list of tuples sorted by keys'
- 'With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)'
- 'Maps are unordered, allow any key type, but disallow duplicate keys'
# List 
Insertion: O(1) for prepending, otherwise O(n)
Deletion: O(1) if first element, otherwise O(n)
- 'Lists are not arrays as in other languages, but single-linked lists'
# Keyword 
# Tuple 
- 'Tuples are better for reading, whereas Lists are better for traversals'
- 'Avoid using tuples as a collection'
'(i.e. avoid Tuple.append/2, Tuple.insert_at/2, or Tuple.delete_at/2)'
# (erlang) array 
Access: O(log n) 
Search: O(log n)
Insertion: O(log n)
Deletion: O(log n)
- 'An array is a trie of small tuples, with a smaller memory overhead to Lists'
# MapSet 
Same complexities as 'Map'
- The time complexities are a mix of
worst complexities. Should we separate them into
best columns maybe?
- Did I forget a data structure? I excluded the Arrays library, because it’s a library that uses different data structures under the hood.
- Should we include ets as well? It has O(1) for access and insertion for
set, bag, and duplicate_bag tables, but isn’t technically a data-structure
- Map in Docs
- Map structure for < 32 and >= 32 elements
- List in Docs
- Tuple in Docs
- Keyword in Docs
- array in erlang Docs
- Complexities of erlang data structures
- MapSet in Docs
Partial overview of complexities
Does Elixir have persistent data structures?
Way to get O(1) access/set
Sequences by @sasajuric
Oh this is a nice initiative
Although it doesn’t mention the complexities explicitly, this article comparing sequences might be an interesting resource to mention as well.
This one would actually be
O(log n), since erlang’s
:arrays are tries (like maps), not actual arrays in the traditional imperative programming sense.
O(log n) amortised - always. If there is less than 32 keys, then these are stored as sorted tuples, which mean, than you can use binary search.
O(log n) (amortised) respectively for less than 32 and more than 32 keys.
In the middle is still
O(1) if first element (just do
tl(list) which is constant)
The same as regular list (as these are the same things) unless you use
Keyword module, which will do deduplication in most cases. Then indeed it will be
It is trie of tuples, so your Big-Os are wrong there.
Thank you very much for your input!
I updated the
List complexities with your info.
I also found this very interesting email which lists the complexities of the erlang data structures. I added the
O(log n) complexity to the
:array section accordingly.
I also removed the
Keyword List to clarify that I mean Elixir’s
I’m not so sure about deletion for
:array, since there isn’t really such an operation.
You could either use
reset/2 to set the value back to the default value (e.g.
:undefined), which would be
O(log n)… but you would end up with a sparse array on which you cannot really use random index anymore, e.g.
[1, 2, :undefined, 4] instead of
[1, 2, 4].
Or you could create a new array with everything except the deleted element, and this would be
That’s a very good point! Unfortunately, I don’t fully understand what you mean with
you cannot use random index anymore (on a sparse array). Would that hurt the time complexity of subsequent actions? Or is this something one has to watch out for during implementation? In that case, I’d still note down
O(log n) and put this under
caveats. What do you think?
Oh sorry, I wasn’t really clear. Strictly speaking you can still use random access in a sparse index, but you would need to account for the “holes”, since the positions and size won’t be shifted. This will impact the rest of your algorithm if you cannot assume a dense array anymore.
> dense_array = delete_at([1, 2, 3, 4], 2)
[1, 2, 4]
> sparse_array = reset_at([1, 2, 3, 4], 2)
[1, 2, :undefined, 4]
The sparse version is just really a
replace_at, not an actual deletion, so it is a bit like comparing apples and oranges. But depending on your algorithm, it is probably the best option in practice when possible, and maybe convert it back to a dense array once you’re done deleting using
I highly recommend adding ets. Digraph is another batteries-included data structure, as is queue. Also counters.
Thank you very much for this clarification. I agree with you that this is a
caveat and should be mentioned in the table. Unfortunately, it seems that you can only edit your posts 24h after publishing them So, I’m unable to adjust the table any more.
@LostKobrakai sorry for the ping. You’re the only moderator that I know. Would it be possible to let me edit my original post a bit longer maybe? I would like to edit the table with the complexities with all recommendations so that we have a single comprehensive source of truth eventually.
Maybe move it to Gist or another externally managed resource, where you will not be limited by the forum editing constraints.
Thank you for the suggestion @hauleth. I moved the table to a GitHub Gist. The gist deviates only slightly from above table (I added a caveat to
array as @sabiwara suggested). I’m happy that above table was quite comprehensive already. I hope it will serve as a good documentation for future reference
GitHub gist: Big-O Time Complexities for Elixir and erlang Data Structures · GitHub