Cost

Quadratic time

A pass for every element, usually a loop inside a loop. The work grows much faster than one scan.

Quadratic time shows up when, for each element, you look at the others. Comparing every pair is the classic picture. Ten elements is a small triangle of comparisons. A thousand elements is a triangle on the order of a million. The input grew by a factor of 100. The work grew by a factor of about 10,000.

Nested loops are the usual way to write this, and they multiply. One loop over n and an inner loop over n is n times n. Sometimes the inner loop shrinks, walking only the rest of the array rather than the whole array. That is still quadratic. The exact count is lower, and Big O drops the constants and the lower-order terms.

A nested loop can still produce the right answer. Counting values below a limit with a pair of loops returns the right number, and it is the habit worth retiring. Naming O(n²) is how you notice that the inner loop was never required.