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 [1]
Access:    O(log n)
Search:    O(log n)
Insertion: O(n) for < 32 elements, O(log n) for >= 32 elements [2]
Deletion:  O(n) for < 32 elements, O(log n) for >= 32 elements [2]
Caveats:
- '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 [3]
Access:    O(n)
Search:    O(n)
Insertion: O(1) for prepending, otherwise O(n)
Deletion:  O(1) if first element, otherwise O(n)
Caveats:
- 'Lists are not arrays as in other languages, but single-linked lists'

# Keyword [4]
Access:    O(n)
Search:    O(n)
Insertion: O(n)
Deletion:  O(n)

# Tuple [5]
Access:    O(1)
Search:    O(n)
Insertion: O(n)
Deletion:  O(n)
Caveats: 
- '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 [6]
Access:    O(log n) [7]
Search:    O(log n)
Insertion: O(log n)
Deletion:  O(log n)
Caveats:
- 'An array is a trie of small tuples, with a smaller memory overhead to Lists'

# MapSet [8]
Same complexities as 'Map'

Discussion points

• The time complexities are a mix of average, best, and worst complexities. Should we separate them into average, worst and 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

References

1. Map in Docs
2. Map structure for < 32 and >= 32 elements
3. List in Docs
4. Tuple in Docs
5. Keyword in Docs
6. array in erlang Docs
7. Complexities of erlang data structures
8. MapSet in Docs

Other resources
Partial overview of complexities
Discussion of :array
Does Elixir have persistent data structures?
Way to get O(1) access/set
Sequences by @sasajuric