They are currently amortized O(1) thanks to breadcrumbing, but there are some caveats in practice. You'll get constant-ish access, but with higher coefficients than if it were natively encoded as UTF-16. You will pay a O(n) scan the very first time you call such a method on the UTF16View. If you mutate the content, that will invalidate the results of the scan, so it will be performed again the next time.
There's a little more written in the blog post and some forum discussions.
Swift String still bridges to NSString lazily, and still services NSString's API in amortized O(1) time with these breadcrumbs. Since NSStrings are often accessed through message sends in the first place (at least without access to implementation details), this amortization cost is not generally significant. When we did performance analysis, we absolutely hammered these public interfaces in app-like scenarios and couldn't measure a reasonable regression. But, in theory, if you could subvert Objective-C message sends and CF bridging checks on NSString, then you might tell the difference.
We hope to speed up the constant factors considerably with SIMD work, which I just filed a bug to track. The savings would allow us to make better performance vs memory tradeoffs. We also don't have any API to expose what the current tradeoff is. If you have any benchmarks or scenarios where you can observe salient performance differences, please let us know.
We don't formally document this guarantee; not until we have a better idea of where opaque or indirect strings might be headed. But, any String that could be lazily bridged to NSString has to provide performance roughly indistinguishable from O(1).
If you want to provide something like a NSTextStorage equivalent, but supporting both modern UTF-8 interfaces and legacy UTF-16 interfaces, you could consider making the backing be contiguous UTF-8 and rely on these breadcrumbs. Obviously, Array<UInt16> would be faster and more direct, but depending on the operation (especially if it's behind a message send), it may not matter. Otherwise, you can also maintain your own mapping between UTF8View indices and UTF16View indices at the cost of greater memory impact.