Skip to content

Instantly share code, notes, and snippets.

@stevencch99

stevencch99/big-o.md

Forked from PJUllrich/big-o.md
Created November 24, 2023 03:28
Download ZIP

Revisions

  1. @PJUllrich PJUllrich revised this gist Jun 13, 2022. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -11,8 +11,8 @@

    **Caveats**:

    - With fewer than 32 elements, a Map is a list of tuples sorted by keys
    - With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
    - 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]](https://hexdocs.pm/elixir/1.12/List.html)
  2. @PJUllrich PJUllrich revised this gist Jun 13, 2022. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -6,8 +6,8 @@
    | --------- | --- |
    | Access | `O(log n)` |
    | Search | `O(log n)` |
    | Insertion | `O(n)` for < 32 elements, `O(log n)` for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520) |
    | Deletion | `O(n)` for < 32 elements, `O(log n)` for >= 32 elements |
    | Insertion | `O(n)` for <= 32 elements, `O(log n)` for > 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520) |
    | Deletion | `O(n)` for <= 32 elements, `O(log n)` for > 32 elements |

    **Caveats**:

  3. @PJUllrich PJUllrich revised this gist Nov 17, 2021. 1 changed file with 11 additions and 1 deletion.
    12 changes: 11 additions & 1 deletion big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -39,8 +39,18 @@ keyword = [{:a, 1}, {:b, 2}]

    **Caveats**

    - 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`.
    - 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`.
    ```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 [[5]](https://hexdocs.pm/elixir/1.12/Tuple.html)

  4. @PJUllrich PJUllrich revised this gist Nov 17, 2021. 1 changed file with 49 additions and 33 deletions.
    82 changes: 49 additions & 33 deletions big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,69 +1,85 @@
    # Big-O Time Complexities for Elixir data structures

    ## Map [[1]](https://hexdocs.pm/elixir/1.12/Map.html)
    | Operation | Time Complexity |
    | --------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
    | Access | O(log n) |
    | Search | O(log n) |
    | Insertion | O(n) for < 32 elements, O(log n) for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520) |
    | Deletion | O(n) for < 32 elements, O(log n) for >= 32 elements |

    | Operation | Time Complexity |
    | --------- | --- |
    | Access | `O(log n)` |
    | Search | `O(log n)` |
    | Insertion | `O(n)` for < 32 elements, `O(log n)` for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520) |
    | Deletion | `O(n)` for < 32 elements, `O(log n)` for >= 32 elements |

    **Caveats**:

    - With fewer than 32 elements, a Map is a list of tuples sorted by keys
    - With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
    - Maps are unordered, allow any key type, but disallow duplicate keys

    ## List [[3]](https://hexdocs.pm/elixir/1.12/List.html)
    | Operation | Time Complexity |

    | 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) |
    | 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 [[4]](https://hexdocs.pm/elixir/1.12/Tuple.html)
    | Operation | Time Complexity |
    | --------- | ------------------------- |
    | Access | O(n) |
    | Search | O(n) |
    | Insertion | O(n) |
    | Deletion | O(n) |
    ## Keyword (List) [[4]](https://hexdocs.pm/elixir/1.12/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}]
    ```

    **Caveats**

    - 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`.
    - A keyword list **does not** guarantee order.

    ## Tuple [[5]](https://hexdocs.pm/elixir/1.12/Tuple.html)

    ## Tuple [[5]](https://hexdocs.pm/elixir/1.12/Keyword.html#module-duplicate-keys-and-ordering)
    | Operation | Time Complexity |
    | --------- | ------------------------- |
    | Access | O(1) |
    | Search | O(n) |
    | Insertion | O(n) |
    | Deletion | O(n) |
    | --------- | --------------- |
    | 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]](https://www.erlang.org/doc/man/array.html)
    | Operation | Time Complexity |

    | 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) |
    | 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)` |

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

    ## MapSet [[8]](https://hexdocs.pm/elixir/1.12/MapSet.html#content)

    ## MapSet [[8]](https://hexdocs.pm/elixir/1.12/List.html)
    Same complexities as 'Map'

    ### 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)
    - [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)
  5. @PJUllrich PJUllrich revised this gist Nov 16, 2021. No changes.
  6. @PJUllrich PJUllrich revised this gist Nov 16, 2021. 1 changed file with 44 additions and 30 deletions.
    74 changes: 44 additions & 30 deletions big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,45 +1,59 @@
    # Big-O Time Complexities for Elixir data structures

    ## Map [[1]](https://hexdocs.pm/elixir/1.12/Map.html)
    Access: O(log n)
    Search: O(log n)
    Insertion: O(n) for < 32 elements, O(log n) for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520)
    Deletion: O(n) for < 32 elements, O(log n) for >= 32 elements
    Caveats:
    | Operation | Time Complexity |
    | --------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
    | Access | O(log n) |
    | Search | O(log n) |
    | Insertion | O(n) for < 32 elements, O(log n) for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520) |
    | Deletion | O(n) for < 32 elements, O(log n) for >= 32 elements |

    **Caveats**:
    - With fewer than 32 elements, a Map is a list of tuples sorted by keys
    - With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
    - Maps are unordered, allow any key type, but disallow duplicate keys

    ## List [[3]](https://hexdocs.pm/elixir/1.12/List.html)
    Access: O(n)
    Search: O(n)
    Insertion: O(1) for prepending, otherwise O(n)
    Deletion: O(1) if first element, otherwise O(n)
    Caveats:
    | 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 [[4]](https://hexdocs.pm/elixir/1.12/Tuple.html)
    Access: O(n)
    Search: O(n)
    Insertion: O(n)
    Deletion: O(n)
    | Operation | Time Complexity |
    | --------- | ------------------------- |
    | Access | O(n) |
    | Search | O(n) |
    | Insertion | O(n) |
    | Deletion | O(n) |

    ## Tuple [[5]](https://hexdocs.pm/elixir/1.12/Keyword.html#module-duplicate-keys-and-ordering)
    Access: O(1)
    Search: O(n)
    Insertion: O(n)
    Deletion: O(n)
    Caveats:
    | 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)
    - (i.e. avoid `Tuple.append/2`, `Tuple.insert_at/2`, or `Tuple.delete_at/2`)

    ## (erlang) array [[6]](https://www.erlang.org/doc/man/array.html)
    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)
    Caveats:
    | 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) |

    **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
    @@ -48,8 +62,8 @@ Caveats:
    Same complexities as 'Map'

    ### 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)
    - [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)
  7. @PJUllrich PJUllrich created this gist Nov 16, 2021.
    55 changes: 55 additions & 0 deletions big-o.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,55 @@
    # Big-O Time Complexities for Elixir data structures

    ## Map [[1]](https://hexdocs.pm/elixir/1.12/Map.html)
    Access: O(log n)
    Search: O(log n)
    Insertion: O(n) for < 32 elements, O(log n) for >= 32 elements [[2]](https://stackoverflow.com/questions/38386314/why-elixirs-mapset-becomes-unordered-after-32-elements/38387520#38387520)
    Deletion: O(n) for < 32 elements, O(log n) for >= 32 elements
    Caveats:
    - With fewer than 32 elements, a Map is a list of tuples sorted by keys
    - With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
    - Maps are unordered, allow any key type, but disallow duplicate keys

    ## List [[3]](https://hexdocs.pm/elixir/1.12/List.html)
    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 [[4]](https://hexdocs.pm/elixir/1.12/Tuple.html)
    Access: O(n)
    Search: O(n)
    Insertion: O(n)
    Deletion: O(n)

    ## Tuple [[5]](https://hexdocs.pm/elixir/1.12/Keyword.html#module-duplicate-keys-and-ordering)
    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]](https://www.erlang.org/doc/man/array.html)
    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)
    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

    ## MapSet [[8]](https://hexdocs.pm/elixir/1.12/List.html)
    Same complexities as 'Map'

    ### 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)