What time complexity measures
Time complexity describes how the work a function does grows as its input grows. It doesn't measure seconds, which depend on the machine. It counts basic steps, such as one comparison or one addition, as a function of the input size, usually called n. Big O notation writes that growth rate in a short form and keeps only the part that dominates for large inputs.
Two rules make the notation simple. Constants are dropped, so 2n + 5 steps is just O(n). Only the fastest-growing term stays, so n² + n is O(n²). For a big enough n, the smaller terms stop mattering.
Linear time: O(n)
A function runs in linear time when its work grows in direct proportion to the input. Doubling the array doubles the steps. The most common pattern is one loop over every element:
func sumAll(_ nums: [Int]) -> Int {
var total = 0
for n in nums {
total += n
}
return total
}
print(sumAll(Array(1...1000)))
print(sumAll(Array(1...2000)))
The output is:
500500
2001000
The loop body runs once per element, so the second call does twice the work of the first. The function is O(n) where n is nums.count. The loop body costs a constant amount per element, and the setup and the return cost a constant amount in total. Constants disappear in Big O, so the whole function is O(n).
Best case and worst case
Big O normally describes the worst case, the input that makes the function do the most work. Consider a linear search:
func countSteps(_ nums: [Int], _ target: Int) -> Int {
var steps = 0
for n in nums {
steps += 1
if n == target { break }
}
return steps
}
On Array(1...1000), searching for 1 takes 1 step, because break ends the loop at once. Searching for 1000 takes 1000 steps, and searching for a value that isn't there, such as -1, also takes 1000 steps. The worst case is the full array, so the function is O(n), even though some inputs finish quickly.
Linear work hidden in library calls
A single line of Swift can hide a loop. These standard calls each visit up to every element, so they are O(n):
contains(_:)andfirstIndex(of:)on an array, which scan until they find the value;min(),max(), andreduce;mapandfilter, which call a closure once per element;insert(_:at:)at the front andremoveFirst()on an array, which shift every remaining element by one position.
Putting such a call inside a loop multiplies the costs. A loop over n elements that calls contains on an array of n elements does up to n × n steps, which is O(n²). Two loops one after the other add instead: O(n) + O(n) is still O(n).
Why it matters
Each lesson in the chapter that follows compares approaches by their growth rate. A linear solution handles a million elements with about a million steps. A quadratic one needs about a million times a million. When you choose between two correct solutions, the lower growth rate is almost always the better one.
Key takeaways
- Big O counts steps as the input size grows, and drops constants and smaller terms.
- One pass over the input is
O(n); a loop that can stop early is stillO(n)in the worst case. - Check what the library calls inside your loops cost, since a hidden linear call turns one loop into
O(n²).
