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
- 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.
- nested loop — A loop placed inside another loop, so the inner body runs once for every combination of the two loop variables.
- insertion sort — A simple sort that takes items one at a time and shifts each left into its correct place among those already sorted.
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
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers