What quadratic time means
An algorithm has quadratic time complexity, written O(n²), when the work grows with the square of the input size. Doubling the input makes it take about four times as long; multiplying it by ten makes it take about a hundred times as long. The classic cause is a loop nested inside another loop, where both run over the input.
The nested loop
func countSteps(_ n: Int) -> Int {
var steps = 0
for _ in 0..<n {
for _ in 0..<n {
steps += 1
}
}
return steps
}
print(countSteps(10), countSteps(100), countSteps(1000))
100 10000 1000000
The outer loop runs n times, and each time the inner loop runs n times, so the body executes n * n times. Growing n by a factor of 10 grows the steps by a factor of 100.
A triangle is still quadratic
Often the inner loop starts after the outer index, so that every pair of positions is visited once. This is the usual shape of "compare every pair of elements":
func countPairs(_ n: Int) -> Int {
var steps = 0
for i in 0..<n {
for _ in (i + 1)..<n {
steps += 1
}
}
return steps
}
print(countPairs(5))
10
The inner loop runs n - 1 times, then n - 2, and so on down to 0, which adds up to n * (n - 1) / 2. For n = 5 that is 10. Big O ignores the constant factor 1/2 and the lower-order term, so this is still O(n²).
In Swift, a range like (i + 1)..<n is valid even when i + 1 equals n; it is just empty. A range whose lower bound is greater than its upper bound, such as 5..<3, stops the program at run time.
A real example: finding a duplicate
To check whether an array contains a repeated value, compare every pair of positions:
func hasDuplicate(_ nums: [Int]) -> Bool {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
if nums[i] == nums[j] { return true }
}
}
return false
}
print(hasDuplicate([4, 1, 7, 1]), hasDuplicate([4, 1, 7]), hasDuplicate([]))
true false false
In the worst case, when there is no duplicate, it makes all n * (n - 1) / 2 comparisons. It uses only a few variables, so the extra space is O(1): quadratic time does not imply quadratic space. Storing the values seen so far in a Set would bring the time down to O(n) at the price of O(n) extra space.
Hidden quadratic loops
The inner loop does not have to be written out. A single loop that calls an O(n) method on each iteration is quadratic too:
for x in a { if a.contains(x) { ... } }scans the array inside every iteration.while !a.isEmpty { a.removeFirst() }shifts the remaining elements each time.for i in 0..<s.countwiths.index(s.startIndex, offsetBy: i)inside walks the string from the start every time.
When you see a loop, ask what each line inside it costs, and multiply.
Two loops in a row are not quadratic
Nesting multiplies; sequence adds. Two separate loops over n elements, one after the other, cost n + n = 2n, which is O(n). Only a loop inside a loop gives n * n.
Why it matters
For 1,000 items a quadratic algorithm does about a million steps, which is instant. For a million items it does about a trillion, which is far too slow. Quadratic solutions are fine for small inputs, but they are often the first version you write, and the next step is to replace the inner loop with something cheaper, such as a set or dictionary lookup, or sorting plus a single pass.
Key takeaways
- A loop nested inside a loop that both depend on
ngivesO(n²). - Visiting each pair once is
n * (n - 1) / 2steps, stillO(n²). - Calling an
O(n)method inside a loop makes the loop quadratic. - Sequential loops add; nested loops multiply.
