What quadratic time means
An algorithm runs in quadratic time, written O(n²), when its running time grows with the square of the input size. Double the input and the work grows about fourfold. Multiply it by ten and the work grows about a hundredfold.
The classic cause is a loop inside a loop where both loops depend on the input size.
The nested loop pattern
static int Steps(int n) {
int steps = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
steps++;
}
}
return steps;
}
The outer loop runs n times, and each time the inner loop runs n times, so the body executes n * n times. Steps(4) returns 16 and Steps(8) returns 64: doubling n multiplied the work by four.
When the inner loop is shorter
The inner loop doesn't have to run all n times for the total to be quadratic. A common variant starts the inner loop after the outer index, so that each pair of positions is visited once:
static int CountPairs(int[] a, int target) {
int count = 0;
for (int i = 0; i < a.Length; i++) {
for (int j = i + 1; j < a.Length; j++) {
if (a[i] + a[j] == target) {
count++;
}
}
}
return count;
}
For { 1, 2, 3, 4, 5 } and target = 6 it returns 2, for the pairs 1 + 5 and 2 + 4.
The inner loop runs n - 1 times for i = 0, then n - 2, and so on down to 0. The total number of comparisons is:
(n - 1) + (n - 2) + ... + 1 + 0 = n * (n - 1) / 2
For n = 10 that is 45 comparisons. Expanding the formula gives n²/2 - n/2. Big O drops constant factors and lower-order terms, so this is still O(n²). Half of a quadratic is a quadratic.
How to recognize it
- Two nested loops that each run a number of times that grows with
n. - Checking every pair of elements, such as finding duplicates or a pair with a given sum by brute force.
- A linear operation inside a linear loop. A loop of
niterations that callslist.Contains(x),list.IndexOf(x)ors.Substring(i)doesO(n)work per iteration, so it is quadratic even though there is only one visible loop. - Printing or building an
nbyngrid, which hasn²cells to produce.
What does not make it quadratic
Two loops one after another are not nested, so their costs add instead of multiplying:
for (int i = 0; i < n; i++) { /* ... */ }
for (int j = 0; j < n; j++) { /* ... */ }
That is n + n = 2n, which is O(n). Nesting is what multiplies.
A nested loop is also not quadratic when the inner loop runs a fixed number of times, for example for (int j = 0; j < 3; j++). Three passes over n elements is 3n, which is O(n). And when a loop halves its counter each time, as in for (int j = n; j > 0; j /= 2), it runs about log₂ n times, so inside a linear loop the total is O(n log n).
When the two loops depend on different inputs, say an array of length n and one of length m, the total is O(n * m). Calling that O(n²) would be wrong unless m is about the same size as n.
Why it matters in practice
Quadratic algorithms are fine for a few thousand elements and painful for a few hundred thousand. An n of 100,000 means around ten billion basic steps, which takes many seconds even in compiled C#. Spotting the pattern early tells you when to look for something better. For the pair-sum example, a HashSet<int> that remembers the values seen so far finds a matching partner in one pass, bringing the time down to O(n) at the cost of O(n) extra space.
Key takeaways
- Nested loops that both grow with
ngiveO(n²). - An inner loop that starts at
i + 1does about half the work, but that half is still quadratic. - Sequential loops add; nested loops multiply.
- A hidden linear call inside a loop, such as
Containson a list, counts as an inner loop. - Doubling the input of a quadratic algorithm roughly quadruples its running time.