Skip to content

Instantly share code, notes, and snippets.

@PJUllrich
Last active June 28, 2024 20:25
Show Gist options
  • Save PJUllrich/4cd3d8e2e8c9170b560e5a501c13c9f3 to your computer and use it in GitHub Desktop.
Save PJUllrich/4cd3d8e2e8c9170b560e5a501c13c9f3 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

@BrooklinJazz
Copy link

I believe a map is O(n) for <= 32 elements. This states that it is O(n) for < 32 elements. Please correct me if I'm wrong, but I doubled checked
by creating a map with 32 elements and it retains sorting order.

Thank you a ton for providing this resource!

@PJUllrich
Copy link
Author

Thanks @BrooklinJazz ! I updated the gist accordingly :)

@inoas
Copy link

inoas commented Oct 23, 2022

By O(log n) do you mean O(log10 n) or the field jargon O(log2 n)?

See: https://en.wikipedia.org/wiki/Logarithm#Particular_bases

@PJUllrich
Copy link
Author

@inoas I'm not sure, but according to this answer, it doesn't really matter since they only differ by a constant factor :)

@SoxFace
Copy link

SoxFace commented May 17, 2023

👏 Thanks for this resource. It’s so well done.

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