dropLast() vs. dropLast(1) for arrays

The documentation of Array.dropLast() states that

Complexity: O(n), where n is the length of the sequence.

whereas the documentation of Array.dropLast(_:) states that

Complexity: O(n), where n is the number of elements to drop.

Does that mean that

let slice = someLargeArray.dropLast()

is less efficient than

let slice = someLargeArray.dropLast(1)

?

Actually I would expect a O(1) implementation (independent of array size and number of elements to drop) since arrays are RandomAccessCollections which allow O(1) index calculations.

O(1) would only be possible if it's an Array of a trivial type, such as Int. If it's an array of e.g. class objects, they need to each be released/destroyed.

edit: scratch that, I was thinking of a mutating drop. Yes, O(n) in documentation is surprising. CC @nnnnnnnn in case he knows.

The Sequence implementation of dropLast(n) has a time complexity of O(n), so I'm guessing that the Array.dropLast documentation has (incorrectly) been "inherited" from Sequence.dropLast. Array.dropLast absolutely has a time complexity of O(1).

Yep, that's the case—those are only declared on either Sequence or Collection, so they need notes about the different performance on BidirectionalCollection and RandomAccessCollection.

Thanks to all. – I filed a bug report: https://bugs.swift.org/browse/SR-7785

1 Like