How is enumerated() constant time O(1)?

Question

I was looking at the documentation for enumerated() on the Array type and noticed that it says:

Complexity: O(1)

https://developer.apple.com/documentation/swift/array/1687832-enumerated

This doesn't seem make sense, as traversing an array would be linear time - O(n) - since the length of the array is not known. enumerated() would have to traverse an array in order to return the EnumeratedSequence. How is this function constant time complexity?

Answer 1

Creating an EnumeratedSequence comes down to initializing its iterator. The latter is done in two steps:

• Have a pointer to the base collection or sequence on which enumerated() is called.
• Initialize the internal variable _count to 0

The time taken to do these two steps doesn't change with the number of elements in the collection/sequence.

Looping through the elements of an EnumeratedSequence is equivalent to calling .next() on the iterator of the EnumeratedSequence. Which creates (on demand) a tuple let result = (offset: _count, element: b) as long as there are elements in the base collection/sequence (hence the guard statement), and increment the _count += 1.

To recapitulate: Creating an enumerated sequence is O(1), but looping through all the elements is of course O(n).