quadratic time

Work that grows with the square of the input, written O(n^2): twice the items, four times the work.

In more detail

Quadratic cost usually comes from a loop inside a loop where both run over the same data, such as comparing every pair of items. It is fine for a few hundred items and painful for a million. Insertion sort on random data and a sequence of front insertions into a list are quadratic.

Related terms

Taught in

References