Quadratic time complexity describes growth proportional to the square of input size. As n increases, the required work can quickly become impractical. section 4.16
A useful picture is the number of pairs in an array: comparing every item with many others creates quadratic growth. Unlike linear or linearithmic growth, this becomes difficult on large inputs. section 4.9 section 4.16
Choosing a sorting algorithm
Selection sort is quadratic, while mergesort and heapsort are linearithmic. For a one-billion-element array, the difference is enormous: quadratic work could take thousands of years, whereas linearithmic work is described as manageable in minutes. section 4.9
How long does it take to run an algorithm? That depends on the order of growth of its running time. All results are approximated.
Use the growth-rate figure to compare how quickly quadratic running time outpaces linear and linearithmic alternatives. section 4.9
