size :: Map k a -> IntSource
O(1). The number of elements in the map.
member :: Ord k => k -> Map k a -> BoolSource
O(log n). Is the key a member of the map? See also notMember.
lookup :: Ord k => k -> Map k a -> Maybe aSource
O(log n). Lookup the value at a key in the map.
> Time complexity: O(N) where N is the number of elements to traverse to get to the element at index. This makes asking for the first or the last element of the list O(1).
I agree this is something more documentations should do when possible; it doesn't even have to be big-O notation as far as I'm concerned, just a "this will iterate over all keys" will be fine.
Ruby's delete() doesn't mention any of this, although you can easily see the (C) implementation in the documentation[2]. In principle at least, this doesn't have to be O(n) if the underlying implementation would be a hash for example, which of course has its own downsides but something like PHP may actually do this with their arrays as they're kind of a mixed data structure? Not sure.
In the C++ standard the complexity of algorithms is a requirement for a compliant implementation. Many text books skip it, but better documentation references it. Taking the "delete element from list" example from this thread https://en.cppreference.com/w/cpp/container/list/remove states that there is a linear search.
Andrei Alexandrescu has a scheme to encode these in the D typesystem on his website. It didn't get merged into the standard library in the end but you can happily do it in your own code
An example would be https://hackage.haskell.org/package/containers-0.4.0.0/docs/....
And so forth...