[SR-428] Implement new performance terminology in documentation

[dabrahams]

Previous ID	SR-428
Radar	rdar://19751259
Original Reporter	@dabrahams
Type	Bug

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Bug, Documentation
Assignee	@natecook1000
Priority	Medium

md5: 27e2fe8cb32c5f7fdcb7599c3d36bbcb

is duplicated by:

• SR-425 Indexable documents startIndex as O(1) but this isn't true for some lazy collections

Issue Description:

Today Swift documentation of algorithmic complexity is in terms of guarantees and requirements. We want to change this, allowing algorithms to be used with data structures that violate current complexity requirements, but otherwise conform semantically to algorithm requirements. This is in no small part motivated by the fact that NSArray makes no performance requirements on its subclass, and we will happily bridge an NSArray with O(N) objectAtIndex into a Swift Array, which conforms to Collection and thus is required to be indexable in O(1).

The plan:

1. Document what are currently complexity requirements on protocols as “Expected complexity:”

2. Document what are currently complexity guarantees as “Complexity:”

3. Make a blanket statement is that components may fail to deliver documented complexity if any of their arguments fail to deliver the expected complexity.

4. Make a blanket statement that unless otherwise specified, types provided by the standard library provide the expected complexity of the protocols to which they conform

5. Document specific exceptions for types such as Array, Set, Dictionary, and String, explaining the conditions under which they fail to deliver expected complexity (e.g. when the backing store is an NSArray subclass with unusual performance characteristics).