Big-O Time Complexities
View Source
Map
| 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
Same complexities as 'Map'
List
| 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)
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}]
# 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/3andKeyword.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
| 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, orTuple.delete_at/2)
- (i.e. avoid
(erlang) array
| Operation | Time Complexity |
|---|---|
| Access | O(log n) [7] |
| 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, which has
O(n)complexity
- For real deletion, use sparse_to_list/1, which has
:queue
| 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
| 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), ? for bag and ordered_bag |
| Length | ?, depends on the decentralized_counters table option (ref) |
:persistent_term
| 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) |
| Length | ? |