LESSON 217 OF 414 · BIG O NOTATION

Quadratic Time Complexity in Rust: Nested Loops and O(n²)

Watch the lesson

Next lesson

RUST · BIG O NOTATION

Time Complexity Practice 3 in Rust, explained

What quadratic time means

An algorithm is quadratic, O(n²), when the work grows with the square of the input size. Double the input and the work quadruples. Multiply the input by ten and the work grows a hundredfold. The usual source is a loop nested inside another loop, where both depend on n.

fn count_steps(n: usize) -> u64 {
    let mut count = 0;
    for _ in 0..n {
        for _ in 0..n {
            count += 1;
        }
    }
    count
}

The inner loop does n iterations, and it runs once for each of the n iterations of the outer loop, so the body runs n × n times:

n = 10    -> 100
n = 100   -> 10000
n = 1000  -> 1000000

Ten times more input gives a hundred times more steps. For n = 100000 that is ten billion steps, which is the point where a quadratic solution stops being usable.

Counting pairs

Many quadratic algorithms compare every element with every other element. With ten numbers, the double loop below visits all pairs of different positions:

let n = v.len();
for i in 0..n {
    for j in 0..n {
        if i != j {
            // compare v[i] and v[j]
        }
    }
}

That visits 90 ordered pairs when v has 10 elements, which is n × (n - 1). Often the order of a pair does not matter, so the inner loop can start after i:

for i in 0..n {
    for j in (i + 1)..n {
        // compare v[i] and v[j]
    }
}

Now each pair is visited once. The inner loop runs n - 1 times, then n - 2, and so on, so the total is (n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2. For 10 elements that is 45, and for 100 elements it is 4950. This looks like an improvement, but half of n² is still proportional to n², and Big O drops the constant 1/2. The algorithm is O(n²) either way.

Hidden quadratic loops

A quadratic algorithm does not need two visible for loops. One loop that calls a linear function in its body is just as quadratic:

A loop over nums that calls seen.contains(&x) on a Vec: up to n comparisons per iteration.
A loop that calls v.insert(0, x) each time: each call shifts all existing elements. Inserting 100 items at the front one after another moves 0 + 1 + ... + 99 = 4950 elements in total.
A loop that calls remove(0), clone() or iter().sum() on the whole collection.
A loop that builds a string with s = format!("{}{}", s, piece), copying everything written so far on every iteration.
A loop that calls s.chars().nth(i) for each position i, where each call walks the string from the start.

The fix is usually a better data structure or a single pass: a HashSet for membership tests, a VecDeque for queues, an in-place append for strings, or a Vec<char> for indexing by character.

Not every nested loop is quadratic

Check what bounds each loop:

If the inner loop runs a fixed number of times, such as for _ in 0..3, the total is 3n, which is O(n).
If the two loops are over different inputs of sizes a and b, the cost is O(a × b), not O(n²).
If the inner loop halves its range each time, the total is O(n log n).
Two loops one after the other, not nested, add: O(n) + O(n) is O(n).

Quadratic time in practice

Quadratic algorithms are often the first correct solution to a problem: compare every pair, check every start and end of a subarray. They are perfectly fine for small inputs. The signal to look for something better is the input limit. If n can reach a hundred thousand or more, an O(n²) solution will be too slow, and you should look for sorting, a hash map or two pointers to bring it down to O(n log n) or O(n).

Common mistakes

Multiplying the counts of unrelated loops. Two separate loops add; only a nested loop multiplies.
Reporting O(n²/2). Drop the constant and write O(n²).
Missing the loop hidden inside a method call.
Using the same name n for two different inputs.

Key takeaways

Quadratic means the work grows with n²: ten times the input is a hundred times the work.
Two nested loops that both depend on n are O(n²), even if the inner loop starts at i + 1.
A linear method call inside a loop over the same data is also quadratic.
Fix it with a hash set or map, a better algorithm, or a single pass.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free