quadratictime

Quadratic time, in the context of computer science, refers to a class of algorithms whose running time grows proportionally to the square of the input size, commonly expressed as O(n^2). The term quadratictime can be used informally to describe both the overall category of such algorithms and any specific implementation whose time complexity is quadratic. A hallmark of quadratic time is that if the input size doubles, the running time roughly quadruples.

Quadratic-time behavior typically arises from operations that require examining all pairs or implementing nested loops over the data. Common sources include simple iterative processes with two levels of looping, such as performing a comparison between every pair of elements or checking for certain conditions across all combinations of elements.

Examples of quadratic-time problems or algorithms include naive all-pairs processing, such as checking every pair for a duplicate or computing pairwise differences, and simple sorting techniques like bubble sort in their straightforward form. While these examples illustrate the concept, many practical tasks in modern software use more efficient approaches to avoid quadratic growth when dealing with large data sets.

Limitations of quadratic time become pronounced as input size grows, making such algorithms impractical for large-scale problems. Optimization strategies aim to reduce time complexity, including sorting followed by linear scans to reduce comparisons, using hash tables to eliminate redundant pairings, or applying divide-and-conquer techniques to achieve near-linear or logarithmic factors (for example, reducing certain problems from O(n^2) to O(n log n) or better in appropriate cases).

See also: time complexity, Big-O notation, quadratic function.