Array complexity

Junior PRO

The gist

Array is a dynamic array: a contiguous buffer with count and capacity, a value type with copy-on-write. All the complexities follow from that.

• Read/write by index — O(1).
• append — amortized O(1); when the buffer is full, a new one of double size is allocated and elements are copied — O(n) for that operation, but rarely.
• insert(_:at:) — O(n): every element to the right shifts. Inserting at the front is the worst case.
• removeLast() / popLast() — O(1).
• remove(at:) / removeFirst() — O(n) (shifting).
• contains, firstIndex(of:) — O(n): linear search.
• count, isEmpty, first, last — O(1).
• Copying let b = a — O(1) (shared buffer); the first mutation of a shared buffer — O(n) because of CoW.

var a = [1, 2, 3]
a.append(4)               // amortized O(1)
a.insert(0, at: 0)        // O(n)
a.removeLast()            // O(1)
a.removeFirst()           // O(n)
_ = a.contains(3)         // O(n)
_ = a[1]                  // O(1)
var b = a                 // O(1): shared buffer
b.append(5)               // O(n): first mutation copies the buffer (CoW)
a.reserveCapacity(1_000)  // so append doesn't reallocate