Why the cost of built-ins matters
A call such as numbers.contains(x) is a single line, but the function behind it may loop over the whole array. The time complexity of your own code includes the cost of every standard function it calls. Knowing these costs lets you read a piece of Swift and see its Big O at a glance.
Arrays
| Operation | Time |
|---|---|
a[i], a[i] = x, count, isEmpty, first, last | O(1) |
append(_:) | O(1) amortized |
removeLast() | O(1) |
insert(_:at:), remove(at:), removeFirst() | O(n) |
contains(_:), firstIndex(of:) | O(n) |
min(), max(), reduce, map, filter | O(n) |
sorted(), sort() | O(n log n) |
The operations that change the front or the middle are linear because the elements after the change have to move over. For example:
var a = Array(1...10)
print(a.removeFirst(), a.count) // 1 9
a.insert(0, at: 0)
print(a) // [0, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Both calls look like one step, and both move every other element. Repeating either one inside a loop over n elements gives O(n²).
Sets and dictionaries
Both store items by hash, so on average, inserting, removing and looking up one item takes O(1). Looking up a key that isn't there gives nil from a dictionary subscript. Iterating over all items is O(n). If you check membership often, converting an array to a Set once costs O(n) and makes each later check O(1) on average, instead of O(n) each.
Strings
countisO(n), because it counts characters.isEmptyisO(1), so use it to test for an empty string.- Strings can't be indexed by integer. Using a
String.Indexis the alternative, but getting the index of the k-th character still walks the string. When you need random access by position, build an array of characters withArray(s), which costsO(n)once. - Joining two strings with
+costs time proportional to the characters copied. Building a result by appending in a loop is fine, but joining the whole accumulated string again at each step adds up.
Sorting
sorted() returns a new sorted array and sort() sorts in place. Both take O(n log n) time. Sorting once and then scanning is often cheaper than comparing every pair: it replaces an O(n²) search with an O(n log n) sort plus an O(n) pass.
Slices
A slice such as a[1...3] is an ArraySlice that shares the original array's storage, so creating one is cheap. Converting it to an array with Array(...) copies the elements and costs O(k) for k elements. A slice keeps the indices of the original array, so a[1...3] starts at index 1, not 0.
let a = [1, 2, 3, 4, 5]
print(a[1...3]) // [2, 3, 4]
print(a[1...3].count) // 3
print(Array(a.dropFirst()).count) // 4
dropFirst() also returns a slice, so only the conversion with Array(...) pays the copying cost. This matters in loops: building a new array from a slice on every iteration makes each step linear.
Reading a function's complexity
Take this code:
func hasDuplicate(_ nums: [Int]) -> Bool {
for i in 0..<nums.count {
if nums[i + 1..<nums.count].contains(nums[i]) { return true }
}
return false
}
The loop runs n times, and each contains call scans up to n elements, so the function is O(n²). Replacing the inner scan with a Set of the values seen so far brings it to O(n), trading extra memory for speed.
Key takeaways
- Index reads,
countandappendon arrays are constant; changes at the front or middle are linear. - Sorting costs
O(n log n);min,max,mapandfiltercostO(n). - Sets and dictionaries give
O(1)average lookups. - A linear built-in inside a loop makes the whole loop quadratic.
