How do you find out how an operation really scales, and which Swift operations that look cheap are quadratic?

21.8.3 · L3 · Interview

Predict first

Which of these grow quadratically when the input is multiplied by four?

import Foundation

func ms(_ f: () -> Void) -> Double {
    let t = DispatchTime.now(); f()
    return Double(DispatchTime.now().uptimeNanoseconds - t.uptimeNanoseconds) / 1e6
}
func best(_ f: () -> Void) -> Double { (0..<3).map { _ in ms(f) }.min()! }
func growth(_ name: String, _ n: Int, _ work: (Int) -> Void) {
    let small = best { work(n) }, big = best { work(4 * n) }
    print(name + ":", big / small > 9 ? "grows quadratically" : "grows linearly")
}
let text = String(repeating: "é", count: 40_000)
growth("append in a loop", 50_000) { n in var a: [Int] = []; for i in 0..<n { a.append(i) } }
growth("a = a + [x] in a loop", 5_000) { n in var a: [Int] = []; for i in 0..<n { a = a + [i] } }
growth("insert(at: 0) in a loop", 5_000) { n in var a: [Int] = []; for i in 0..<n { a.insert(i, at: 0) } }
growth("s[s.index(startIndex, offsetBy: i)] per i", 1_000) { n in
    let s = String(text.prefix(n)); var c = 0
    for i in 0..<n { c += s[s.index(s.startIndex, offsetBy: i)] == "é" ? 1 : 0 }
}
growth("for ch in s", 1_000) { n in let s = String(text.prefix(n)); var c = 0; for ch in s { c += ch == "é" ? 1 : 0 } }

append, a = a + [x] and for ch in s: linear; insert(at: 0) and offsetBy per index: quadratic
All five are quadratic
Only a = a + [x] is quadratic

Mental model. Checking a road’s speed limit by driving ten and forty miles and comparing the times, instead of trusting the sign.

Do not guess the complexity of a call; measure at n and 4n. If the time grows about four-fold the loop is linear, if it grows about sixteen-fold it is quadratic. Take the best of a few runs, pick sizes where the small case takes at least a millisecond, and print only the classification. In the check, a loop of append and a plain for ch in s grew linearly, while insert(_, at: 0) in a loop (each insert shifts every element) and s[s.index(s.startIndex, offsetBy: i)] for every i (each offset walks the string from the start, because String indices are not random access) grew quadratically.

The surprise is in the other direction too. a = a + [x] looks like it copies the array each time, and the Swift manual-era advice says it is quadratic, but in this Swift 6.4 -O build it grew linearly: the optimiser rewrote it. That is exactly why you measure instead of reciting folklore, and why you re-measure after compiler upgrades. When something is quadratic, the fixes are structural: iterate once instead of indexing by offset, keep a running Index, use a deque or reversed storage for front insertion, or build with append and reserveCapacity (Q69). Remember a quadratic loop is invisible at 100 items and a hang at 100,000, so test with production-sized data.

Front insertion and offset-based string indexing are quadratic; the optimiser removes the cost of a = a + [x].

Common traps

Benchmarking one size. A quadratic cost looks fine until the data grows.
Repeating folklore about copies. The optimiser changes the answer; the experiment is the authority.

They might follow up with

How do I iterate a string by position cheaply? Keep and advance an index, or convert once to an array of Character if you need random access.
Can I put this in CI? A ratio check with a generous margin catches an accidental O(n²) without being flaky about absolute time.

How do you find out how an operation really scales, and which Swift operations that look cheap are quadratic?

Predict first

Common traps

They might follow up with

Related questions