underestimatedCount complexity documentation is broken

[dabrahams]

Description

  /// - Complexity: O(1), except if the sequence also conforms to `Collection`.
  ///   In this case, see the documentation of `Collection.underestimatedCount`.

This was done in ea49459b7594 The correct complexity bound is O(N) where N is the length of the sequence.

The current wording is meaningless, other than to say the complexity bound is O(N) (as given by Collection's requirements). When you are handling a Sequence, (modulo dynamic casts that you couldn't even perform when that change was made and that nobody does in practice), you don't know that it isn't a Collection. Furthermore, nearly any Sequence can be made to conform to Collection post-hoc. I don't know what made anyone think they could tighten a complexity bound on an existing protocol, but (obviously) when you do that you break anyone that had a previously-valid conformance. More generally, it is broken and wrong to loosen constraints in a refinement. In this case that would make every Collection not-a Sequence.

Reproduction

Read the docs.

Expected behavior

The docs make sense and are meaningful.

Environment

Any environment you like

Additional information

No response

[jamiejamesjk]

I really agree with your points.

I feel like Collection.underestimatedCount shouldn't return count like it currently does. And underestimatedCount should be required to be O(1)--or at least sublinear.

Otherwise, it seriously defeats the purpose of using underestimatedCount in the first place. I feel like nearly every instance of people using underestimatedCount has come from the need to reserve capacity beforehand, but if it takes O(n) time and an iteration over the collection to do that, then it really isn't worth it.