That's a pretty good summary. If I were to make a table, I'd probably focus on a handful of expectation buckets expectation which is more general - constant, sublinear, or linear.
The other thing to know is that there are some important interfaces (exposed by predicate functions) that hint to performance classes as well. For example, Counted (check with `counted?`) says whether it can be counted in constant time and that divides the two behaviors you see on that line. Similarly, Indexed and `indexed?` and nth.
And then an important takeaway is that if a data structure can't implement an operation within the expectation constraint, we don't implement it. nth and count are kind of special exceptions as they are polymorphic across those classes above.