Skip to content

Instantly share code, notes, and snippets.

@scottming
Forked from PJUllrich/big-o.md
Created September 13, 2022 13:33
Show Gist options
  • Save scottming/1566fc17a03bb186de146b6eac7b6f75 to your computer and use it in GitHub Desktop.
Save scottming/1566fc17a03bb186de146b6eac7b6f75 to your computer and use it in GitHub Desktop.
Big-O Time Complexities for Elixir Data Structures

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 and 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

MapSet [8]

Same complexities as 'Map'

References

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment