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).
Elixir has a convention where
_length means O(n), and
_size means O(1)