Quadratic time complexity, written O(n²), means an algorithm’s operation count grows with the square of its input size. It can become slow as inputs grow, so compare growth in operations rather than elapsed seconds. section 1.10
A repeated scan is a common path to quadratic time:
- Selection sort finds the next highest-played artist by scanning the list, then repeats the scan. Doing an O(n) scan n times gives O(n²). section 2.9
- Quicksort takes O(n²) in the worst case when its call stack has O(n) levels and each level touches O(n) elements. section 4.5
Selection sort checks fewer elements on later scans, but its total work is still O(n²): the average scan is about half the list, and Big O ignores that constant factor. Quicksort can also have quadratic worst-case time, even though its average time is O(n log n). section 2.9 section 4.3
