What O(1) means
An operation runs in constant time, written O(1), when the work it does doesn't depend on the size of the input. Reading one element from an array of ten items and reading one from an array of ten million are the same amount of work. The name doesn't mean the operation is fast in absolute terms, only that it doesn't slow down as the data grows.
Constant-time operations on Swift arrays
var a = Array(1...10)
print(a.count) // 10
print(a.first!) // 1
print(a.last!) // 10
print(a[5]) // 6
a.append(11)
print(a.removeLast()) // 11
- Reading by index:
a[5]goes straight to the position, because array elements are stored next to each other in memory. - Writing by index:
a[5] = 0replaces one element. count,isEmpty,firstandlast: the array already knows its length and where its ends are.append: amortizedO(1). Usually it writes into free space at the end. Occasionally the array has to move to a bigger block of memory, which takesO(n). That growth is rare enough that the average cost per append stays constant.removeLast(): takes the last element out without moving anything else.
Constant time elsewhere
let s: Set = [1, 2, 3]
print(s.contains(2)) // true
let d = ["a": 1]
print(d["a"] as Any) // Optional(1)
print(d["z"] as Any) // nil
- Dictionary and Set lookups:
containson aSetand a dictionary subscript use hashing, so on average they areO(1), however many items are stored. A missing key givesnilfor a dictionary subscript. - Arithmetic and comparisons:
n % 2 == 0anda + bare constant. They take the same time for any value that fits in anInt. - Variable assignment and function calls that only do the above.
Operations that look constant but are not
removeFirst()andinsert(_:at: 0)on an array shift every other element, so they areO(n).containson an array scans the elements and isO(n). On aSetit isO(1)on average.String.countisO(n), because Swift counts characters, and a character can take several bytes. For the string"héllo",countis 5 whileutf8.countis 6.- Array indexing is by
Int, but strings are not. AStringcan't be indexed with an integer for this reason; useArray(s)when you need random access.
Why arrays can jump straight to an index
An array stores its elements one after another in a single block of memory, and every element has the same size. The position of element i is then the start of the block plus i times the element size, one multiplication and one addition, no matter how large i is. A dictionary reaches a value differently: it turns the key into a number with a hash function, and that number says which slot to look at. Both approaches skip the scan through the other items, which is where the constant time comes from.
Counting constant work
A function whose body has no loops and calls only constant-time operations is O(1) overall:
func firstElement(_ nums: [Int]) -> Int? {
return nums.first
}
A loop that always runs a fixed number of times, such as for i in 0..<3, is also constant, because the count doesn't depend on the input. A constant is not the same as small: a loop that always runs a million times is O(1), though it is slow.
Key takeaways
O(1)means the cost doesn't depend on the input size.- Array indexing,
count,first,last,append(amortized) andremoveLastare constant time. - Set and dictionary lookups are constant on average.
- Operations that shift elements, scan, or count characters are linear.
