Quadratic (O(n²))

At a glance: The work or stored cell count grows proportionally to the square of input size.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

Checking every possible ordered pair in a group of n objects requires n × n comparisons if each pair costs the same. A square grid with n rows and n columns contains the same number of cells.

Doubling the input from n to 2n multiplies the number of ordered pairs by four: (2n)² = 4n². Testing only unordered distinct pairs produces n(n-1)/2, which is still Θ(n²), because the leading term is quadratic.

Counting pairs creates a square

For each of n elements, a program may compare it with every one of the n elements, giving n × n = n² comparisons. This includes self-pairs and considers (a,b) different from (b,a). If you only examine unordered distinct pairs, the count is n(n-1)/2. The factor of one half and the lower-order -n term do not change Θ(n²).

Quadratic work also appears in certain input-dependent sorting algorithms. A simple insertion sort can shift up to i earlier elements when placing the element at position i; summing 1 + 2 + ... + (n-1) produces Θ(n²) moves in the worst case. Yet insertion sort can be linear on already sorted data, showing why the input arrangement and the requested case matter.

Do not infer quadratic complexity from indentation alone. Two nested loops with different bounds may do only Θ(n) total work if an index never resets, or Θ(n log n) if the inner loop halves its range.

Worked example

For 10 items, there are 100 ordered pairs. For 20, there are 400. For 100, there are 10,000. This is why quadratic algorithms may look fine for small classroom examples yet become expensive on large inputs.

Compare ordered and unordered pairs

With four people, examining every ordered pair (including a person paired with themselves) creates 16 visits. If the task is instead to ask whether every distinct pair knows each other, there are only 4 × 3 / 2 = 6 checks: (A,B) is the same relationship as (B,A). At 100 people, those counts become 10,000 and 4,950. Both grow quadratically as the group expands.

Doubling the number of people from 100 to 200 raises the ordered checks from 10,000 to 40,000. The unordered count grows from 4,950 to 19,900, almost fourfold. The exact totals differ, but the asymptotic growth agrees.

Time complexity

Representative time example: All pairs of elements.

Two complete nested loops each execute n iterations, for a total of n² calls to the inner operation. This assumes the compared operation itself costs O(1). Some pairwise comparisons on variable-length strings take additional time, and then n² loop iterations alone do not describe the whole algorithm. If an inner loop stops early or depends on i, calculate the actual sum rather than blindly multiplying loop limits.

Derive a nested-loop bound

For two loops each running exactly n times, the inner operation executes n times for each of n outer iterations: Θ(n²). If the inner loop begins at j = i + 1, its iterations are n-1, n-2, ..., 0, totaling n(n-1)/2; the class remains quadratic. If the inner operation itself scans an array, the full work could rise to Θ(n³).

For insertion sort, worst-case shifts form a triangular sum, but the best-case for a sorted input is only Θ(n) because each element needs one comparison. Asking for one complexity class without saying worst case, best case or average case can hide important behavior. Also distinguish an inner loop whose progress persists across outer iterations: that pattern can be linear despite nested syntax.

C#

C# | Quadratic.cs

for (int i = 0; i < values.Length; i++)
    for (int j = 0; j < values.Length; j++)
        Compare(values[i], values[j]);

C++

C++ | quadratic.cpp

for (std::size_t i = 0; i < values.size(); ++i)
    for (std::size_t j = 0; j < values.size(); ++j)
        compare(values[i], values[j]);

Analysis: Two full n-sized nested loops yield O(n²) calls, assuming Compare costs O(1).

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: An adjacency matrix.

An n × n boolean matrix holds n² cells and therefore has O(n²) space. Graph adjacency matrices are a practical example when vertices are indexed, though whether a matrix is auxiliary memory or a chosen input representation depends on the API. The pair-checking nested loops themselves usually require only two counters, which is O(1) auxiliary space. Work count and allocated cells must be analyzed independently.

A pairwise loop is not a pairwise matrix

The loop that compares pairs may retain only two indices and a temporary comparison result, giving Θ(1) auxiliary memory even while doing Θ(n²) work. Allocating an n × n adjacency matrix is a separate design decision that keeps Θ(n²) cells live. Such a matrix lets the program ask whether an edge exists by direct indexing, typically O(1) time for that query.

For a sparse graph with n vertices and e edges, an adjacency-list representation can use Θ(n + e) storage instead. The matrix remains convenient for dense graphs or repeated direct edge queries, but may waste memory when only a few pairs are connected. The memory bound depends on what is stored, not on the number of loop levels.

C#

C# | Quadratic.cs

bool[,] seen = new bool[n, n];

C++

C++ | quadratic.cpp

#include <vector>

std::vector<std::vector<bool>> seen(n, std::vector<bool>(n));

Analysis: An n × n matrix uses O(n²) auxiliary space; two nested loops alone do not imply O(n²) space.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Where quadratic algorithms make sense

Quadratic algorithms can be reasonable for small inputs, simple code or problems that inherently require reporting Θ(n²) relationships. If the output consists of all pairs, writing it already requires Ω(n²) time. If you only need to find duplicates, though, hashing or sorting might reduce repeated pairwise comparisons, at the price of different assumptions or extra memory.

For sorting, compare a straightforward quadratic insertion algorithm against merge sort’s Θ(n log n) worst-case bound. Insertion sort can nevertheless win on tiny or nearly sorted arrays due to excellent locality and low overhead. Big O describes growth, not an unconditional ranking of every real-world workload.

Practical example: checking every pair of entities

A naive game system might test every unit against every other unit to detect nearby interactions. With n units, an all-pairs check performs Θ(n²) comparisons, whether or not most units are far apart. If interaction is symmetric, considering only i < j avoids duplicate tests and roughly halves the work, but it does not change the asymptotic class.

A spatial grid, quadtree or another broad-phase structure can reduce the number of candidate pairs in many scenes, although its guarantees depend on entity distribution and implementation. The pairwise loop itself might use only constant extra storage, while a saved collision matrix consumes Θ(n²). This is why both the cost of finding candidates and the storage of results deserve separate analysis.

Common mistake

Watch out: Nested loops do not always mean O(n²). If the inner index continues from where it stopped, the combined number of iterations may be linear. Analyze iteration ranges before choosing a class.

Try it yourself

Count both ordered and unordered pairs for n = 5, then determine how many bytes an n × n byte matrix would use.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes