What quadratic time means
An algorithm has quadratic time complexity when the work it does grows with the square of the input size. Double the input and the work roughly quadruples. Multiply the input by 10 and the work grows by about 100. In Big O notation this is written O(n²), or O(n^2) in plain text.
The classic source of quadratic time is a nested loop: an outer loop that runs about n times, and an inner loop that also runs about n times for every pass of the outer one. The body of the inner loop then runs n * n times.
Counting the steps in Go
This function counts how many times the inner body runs for an input of size n:
func countPairs(n int) int {
count := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
count++
}
}
return count
}
Go has only one loop keyword, for, so every nested loop in Go is a for inside a for. Running the function for three sizes gives:
n = 10 count = 100
n = 100 count = 10000
n = 1000 count = 1000000
Each time n is multiplied by 10, the count is multiplied by 100. That is the signature of O(n²).
A realistic example: checking every pair
Suppose you want to know whether two numbers in a slice add up to target. The direct approach tries every pair:
func hasPairSum(nums []int, target int) bool {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i]+nums[j] == target {
return true
}
}
}
return false
}
The inner loop starts at i + 1, so each pair is looked at once and no element is paired with itself. For a slice of 5 elements and a target that doesn't occur, the comparison runs 4 + 3 + 2 + 1 = 10 times. In general it runs n * (n - 1) / 2 times. Expand that and you get n²/2 - n/2.
Big O keeps only the fastest-growing term and drops constant factors, so n²/2 - n/2 is still O(n²). Looping over "half" of the pairs is not an improvement in complexity class. For a slice of 1,000 elements, the loop makes 499,500 comparisons, and for 100 elements it makes 4,950: again about 100 times more work for 10 times more data.
Best case and worst case
Big O usually describes the worst case. If hasPairSum is called with []int{1, 2, 3, 4, 5} and a target of 3, it returns after a single comparison, because 1 + 2 is the first pair it tries. With a target of 100 it makes all 10 comparisons and returns false. The function is still called O(n²), because that is the most work it can ever do for an input of that size.
What is not quadratic
Two nested loops do not always mean O(n²), and quadratic time doesn't always need nesting. Look at how many times the loops actually run.
- Two loops one after the other add up instead of multiplying. Two separate loops of
nsteps each do2nsteps, which isO(n). - A nested loop whose inner part is short may be cheaper. If the inner loop always runs a fixed 3 times, the total is
3n, which isO(n). - Different sizes give a product of two different quantities. A loop over the rows of a grid with an inner loop over the columns is
O(rows * columns). It is onlyO(n²)when both sides are aboutn. - Hidden loops count too. In Go,
len(nums)on a slice or a string is constant time, but copying a slice, comparing two long strings or searching a slice by hand each take time proportional to their length. Putting one of these inside a loop overnelements makes the whole thing quadratic.
String concatenation in a loop
A common hidden quadratic in Go is building a string with += inside a loop. Go strings are immutable, so each s += "ab" creates a new string and copies the old contents into it. After n appends the total number of bytes copied grows with n². For small loops this doesn't matter. For large ones, collect the pieces with strings.Builder, which appends into a growing buffer.
Doing better
Many quadratic algorithms can be improved by trading memory for time. hasPairSum can remember each number it has seen in a map and, for every new number, ask whether target - v is already there:
func hasPairSum(nums []int, target int) bool {
seen := map[int]bool{}
for _, v := range nums {
if seen[target-v] {
return true
}
seen[v] = true
}
return false
}
A map lookup takes constant time on average, so a single loop over n elements gives O(n) time. The price is O(n) extra memory for the map. Reading a missing key gives the zero value, which is false for a bool map, so seen[target-v] is safe without a separate check.
Why it matters
Quadratic algorithms are fine for small inputs and become slow quickly. With 1,000 elements, O(n²) means about a million steps, which a computer finishes at once. With a million elements it means about a trillion steps, which is far too many. When you see a nested loop over the same data, ask whether a map, sorting or a single pass could replace the inner loop.
Key takeaways
- Quadratic time,
O(n²), means work proportional ton * n. Ten times more data means about a hundred times more work. - The usual cause is a loop nested in another loop, both running about
ntimes. - Loops over "half" of the pairs, such as
j := i + 1, still count asO(n²), because constant factors and lower terms are dropped. - Sequential loops add and do not multiply, so two loops in a row are
O(n). - Watch for hidden loops, such as
+=on strings inside a loop. - A map often turns a pair search from
O(n²)intoO(n).