Big-O Time Complexities for Elixir Data Structures

big-o.md

Big-O Time Complexities for Elixir data structures

Map [1]

Operation	Time Complexity
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

Caveats:

• With 32 or fewer elements, a Map is a list of tuples sorted by keys
• With more than 32 elements, a Map is a Hash Array Mapped Trie (HAMT)
• Maps are unordered, allow any key type, but disallow duplicate keys

List [3]

Operation	Time Complexity
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 (List) [4]

A Keyword (list) has the same time complexities as List. Every entry in a Keyword (list) is a tuple with the first element being the key and the second element the value.

keyword = [{:a, 1}, {:b, 2}]

Caveats

• A keyword list does not guarantee order.
• A keyword list may have duplicate keys, but duplicates are often ignored by functions like Keyword.get/3 (returns the first match) and are even removed by e.g. Keyword.put/3 and Keyword.delete/2.

iex> Keyword.get([{:a, 1}, {:a, 2}], :a)
1

iex> Keyword.put([{:a, 1}, {:a, 2}], :a, 3)
[a: 3]

iex> Keyword.delete([{:a, 1}, {:a, 2}], :a)
[]

Tuple [5]

Operation	Time Complexity
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]

Operation	Time Complexity
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
• Deletion is actually a replace with the default value and creates sparse arrays
  • For real deletion, use sparse_to_list/1, which has O(n) complexity

MapSet [8]

Same complexities as 'Map'

References

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