nested loop

A loop placed inside another loop, so the inner body runs once for every combination of the two loop variables.

In more detail

When both loops run over the same n items, the inner body runs n times n times, giving quadratic cost. Counting how many times the innermost line runs is the quickest way to read the growth rate of such code. Replacing the inner loop with a dict or set lookup often turns quadratic code into linear code.

Related terms

Taught in

References