# Big-O Time Complexities ## [Map](https://hexdocs.pm/elixir/1.17/Map.html) | Operation | Time Complexity | | --- | --- | | Access | `O(log n)` | | Search | `O(log n)` | | Insertion | `O(log n)` | | Deletion | `O(log n)` | | Size | `O(1)` | **Caveats**: - Maps are unordered, allow any key type, but disallow duplicate keys ## [MapSet](https://hexdocs.pm/elixir/1.17/MapSet.html) Same complexities as 'Map' ## [List](https://hexdocs.pm/elixir/1.17/List.html) | 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)` | | Length | `O(n)` | **Caveats** - Lists are not arrays as in other languages, but single-linked lists ## [Keyword (List)](https://hexdocs.pm/elixir/1.17/Keyword.html#module-duplicate-keys-and-ordering) 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`. ```elixir keyword = [{:a, 1}, {:b, 2}] # Can also be written as: keyword = [a: 1, b: 2] ``` **Caveats** - Keys must be atoms. - Keys are ordered, as specified by the developer. - 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`. ```elixir 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](https://hexdocs.pm/elixir/1.17/Tuple.html) | Operation | Time Complexity | | --- | --- | | Access | `O(1)` | | Search | `O(n)` | | Insertion | `O(n)` | | Deletion | `O(n)` | | Length | `O(1)` | **Caveats** - Tuples are better for reading, whereas Lists are better for traversals - Avoid using tuples as a collection - (i.e. avoid `Tuple.insert_at/3`, or `Tuple.delete_at/2`) ## [(erlang) array](https://www.erlang.org/doc/man/array.html) | Operation | Time Complexity | | --- | --- | | Access | `O(log n)` [[7]](https://erlang.org/pipermail/erlang-questions/2015-September/086001.html) | | Search | `O(log n)` | | Insertion | `O(log n)` | | Deletion | `O(log n)` | | Length | `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](https://www.erlang.org/doc/man/array.html#sparse_to_list-1), which has `O(n)` complexity ## [:queue](https://www.erlang.org/doc/apps/stdlib/queue.html) | Operation | Time Complexity | | --- | --- | | Access | `O(1)` for first and last element, `O(n)` otherwise | | Search | `O(n)` | | Insertion | `O(1)` | | Deletion | `O(n)` | | Length | `O(n)` | ## [:ets](https://www.erlang.org/doc/apps/stdlib/ets.html) | Operation | Time Complexity | | --- | --- | | Access/Search/Insertion | `O(1)` for `set`, `O(log n)` for `ordered_set` where `n` is the table size, `O(n)` for `bag` and `duplicate_bag` where `n` is the number of duplicate keys | | Deletion | `O(1)` for `set`, `O(n)` for `ordered_set` [(ref)](https://erlang.org/workshop/2003/paper/p43-fritchie.pdf), ? for `bag` and `ordered_bag` | | Length | ?, depends on the `decentralized_counters` table option [(ref)](https://www.erlang.org/doc/apps/stdlib/ets.html#info/1) | ## [:persistent_term](https://www.erlang.org/doc/apps/erts/persistent_term.html) | Operation | Time Complexity | | --- | --- | | Access | `O(1)`| | Search | `O(1)`| | Insertion | `O(n)` where `n` is the number of references to the term | | Deletion | Just don't [(ref)](https://www.erlang.org/doc/apps/erts/persistent_term.html) | | Length | ? | ### References - [Partial overview of complexities](https://stackoverflow.com/questions/46385207/closest-thing-to-arrays-in-elixir/46476693#46476693) - [Discussion of :array](https://elixirforum.com/t/arrays/8850) - [Does Elixir have persistent data structures?](https://stackoverflow.com/questions/30203227/does-elixir-have-persistent-data-structures-similar-to-clojure) - [Way to get `O(1)` access/set](https://elixirforum.com/t/way-to-get-o-1-access-set/24471/3) - [Sequences by sasajuric](https://www.theerlangelist.com/article/sequences)