Big-O Time Complexities

guides/09-misc/big-o.livemd

Peter Ullrich

@PJUllrich

run-elixir

More notebooks

Big-O Time Complexities

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

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.append/2, Tuple.insert_at/3, or Tuple.delete_at/2)

(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

: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	?

References

Back