Why the cost of a method matters
Every line of Swift you write has a cost that depends on the size of its input. A call that touches one element takes the same time for ten items or ten million. A call that visits every element takes a million times longer on a million items. Big O notation describes this growth, and knowing the cost of the standard array and string methods lets you predict how a whole program scales before you run it.
Array methods
With n as the number of elements, these are the costs to remember:
| Operation | Cost | Why |
|---|---|---|
a[i], a.count, a.first, a.last | O(1) | Arrays are contiguous, so the position is computed directly. |
a.append(x) | O(1) amortized | Usually it writes into spare capacity; occasionally the array grows and copies everything. |
a.removeLast() | O(1) | Nothing has to move. |
a.insert(x, at: 0), a.removeFirst() | O(n) | Every other element shifts by one position. |
a.contains(x), a.firstIndex(of: x) | O(n) | They may scan the whole array. |
a.sorted(), a.sort() | O(n log n) | Comparison sorting. |
var a = [1, 2, 3]
a.append(4) // [1, 2, 3, 4], cheap
a.insert(0, at: 0) // [0, 1, 2, 3, 4], shifts all four elements
let first = a.removeFirst() // 0, shifts the rest back
let last = a.removeLast() // 4, cheap
print(first, last, a)
0 4 [1, 2, 3]
The practical rule: work at the end of an array, not at the front. A loop that calls removeFirst() on every iteration is quadratic, even though each line looks harmless.
String methods
A Swift String is a sequence of Character values, and one character can span several bytes. Because of that, a string can't be indexed with an integer, and count is not free: it has to walk the text and count characters, so it is O(n). Moving to the character at offset k with s.index(s.startIndex, offsetBy: k) is O(k) for the same reason.
let s = "héllo"
print(s.count, s.utf8.count)
let idx = s.index(s.startIndex, offsetBy: 2)
print(s[idx])
5 6
l
The string has 5 characters but 6 bytes in UTF-8, since é takes two. A loop such as for i in 0..<s.count that calls index(_:offsetBy:) inside is quadratic. When you need random access, convert once with Array(s), which costs O(n), and then every chars[i] is O(1).
Dictionaries and sets are different from arrays: d[key], set.contains(x) and inserting are O(1) on average, which is why they are the usual tool for replacing an O(n) contains on an array.
What a logarithm is
The logarithm base 2 of n, written log n, answers the question: how many times can you halve n before you reach 1? For 8 the answer is 3 (8, 4, 2, 1). Whenever an algorithm throws away half of the remaining work at each step, its running time is O(log n).
func halvings(_ n: Int) -> Int {
var count = 0
var x = n
while x > 1 {
x /= 2
count += 1
}
return count
}
print(halvings(8), halvings(1000), halvings(1_000_000), halvings(1_000_000_000))
3 9 19 29
A billion items need only 29 halvings. That is why logarithmic algorithms are considered nearly as good as constant time.
Binary search
Binary search is the standard example. On a sorted array, look at the middle element: if it is the target, you are done; if it is smaller, the target can only be in the right half; otherwise in the left half. Each step halves the range.
func binarySearch(_ arr: [Int], _ target: Int) -> Int {
var lo = 0, hi = arr.count - 1
while lo <= hi {
let mid = lo + (hi - lo) / 2
if arr[mid] == target { return mid }
if arr[mid] < target { lo = mid + 1 } else { hi = mid - 1 }
}
return -1
}
print(binarySearch([1, 3, 5, 7, 9, 11], 7), binarySearch([1, 3, 5], 4))
3 -1
It only works because indexing an array is O(1). On a structure where reaching the middle costs O(n), the saving disappears.
Key takeaways
- Indexing an array and appending are cheap; inserting or removing at the front, and searching with
contains, areO(n). - Swift strings have no integer index, and
countisO(n). UseArray(s)when you need positions. O(log n)means the input is halved at each step, as in binary search.- Dictionary and set lookups are
O(1)on average.
