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
- quadratic time — Work that grows with the square of the input, written O(n^2): twice the items, four times the work.
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers