Does length() have to count the elements of a list one by one, i.e. O(n), or does it have some sort of optimization so that it is O(1)? I couldn’t find this in the docs.
Its O(n). Implemented as a BIF, but still O(n).
2 Likes
Elixir has a convention where _length
means O(n), and _size
means O(1)
https://hexdocs.pm/elixir/naming-conventions.html#length-and-size
15 Likes