Nested loops imply quadratic explosions

Beginner Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

A double loop over indices (i, j) with i, j < n runs Θ(n²) iterations if the inner body is O(1). That pattern appears in brute-force duplicate detection, naive all-pairs distance matrices before vectorisation, and “for each user, for each item” prototypes that never scale.

Pandas merge on non-indexed keys and accidental Cartesian products can explode row counts the same way—logical nested structure, not just literal for loops. Before optimising inner arithmetic, ask whether the pairing strategy is fundamentally quadratic.

When the problem truly needs all pairs, you either pay quadratic time, use sampling, or restructure (spatial data structures, blocking, matrix algebra).

Time complexity primer: [1].

Sources

[1]https://docs.python.org/3/tutorial/stdlib.html#brief-tour-of-the-standard-library Return to text

University approvals: 0

Tasks

Question 1

What is the Big-O of the inner body iteration count for:

for i in range(n):
    for j in range(n):
        pass

Hint

n outer iterations × n inner iterations.

O(n)

O(n log n)

O(n²)

O(2^n)

Question 2

You compute pairwise cosine similarity between all embedding rows with nested Python loops over n vectors. For large n, what is the honest scaling of the pair enumeration itself (ignoring constant inner math)?

Hint

All unordered or ordered pairs of rows.

O(n)

O(n log n)

O(n²)

O(1) if vectors are normalized

Question 3

pair_hits(vals) counts pairs (i, j) with i < j and vals[i] == vals[j] (ints). Brute-force double loop; O(n²) is fine for this exercise.

Hint

Let j start at i+1 to enforce i<j once.

def pair_hits(vals):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Beginner
Completed: 0 users

Creator

Pavel