What is the BigO of Swift's String.count?

Question

When swift uses String.count is it:

O(n) where each time we call it we iterate through the entire String in order to count it

or

O(1) where swift has previously stored the size of this array and simply accesses it.

Answer 1

It is definitely O(n). From the Swift Book:

As a result, the number of characters in a string can't be calculated without iterating through the string to determine its extended grapheme cluster boundaries. If you are working with particularly long string values, be aware that the count property must iterate over the Unicode scalars in the entire string in order to determine the characters for that string.

This has a few implications, the biggest of which is integer subscripting (i.e. str[5]) is not available through the standard library. Internally, String uses ASCII or UTF-16 encoding (from Swift 5, it uses UTF-8 only). If the string only uses ASCII characters then count can be O(1) but ASCII only has 127 characters so consider this an exception rather than the rule.

NSString, on the other hand, always uses UTF-16 so accessing its length is O(1). And also keep in mind that NSString.length != String.count (try strings with emojis and you'll see).

As for your second question, it does not cache count for subsequent calls. Every call to count is thus O(n), even if the string has not changed. The code in the Foundation repo also confirms that.