Quadratic time complexity describes a cost proportional to the square of an input’s size. When the problem doubles, the cost quadruples; a tenfold increase makes it roughly one hundred times larger. section 1.1
Use the growth pattern to compare quadratic work with nearby complexity classes:
- Linear work doubles when the input doubles, while quasilinear work grows slightly faster than doubling. section 1.1
- Quadratic work becomes increasingly steep as input size grows, so it is usually unsuitable for large, scalable problems. section 1.1 section 1.4
- Some implementations become quadratic accidentally when a cheaper design is available. section 1.1
Repeated string concatenation
A naïve ToString implementation that repeatedly appends to an accumulating string copies the accumulated text each time. The result is O(n²) in both time and extra memory; replacing it with StringBuilder yields an O(n) implementation. section 1.2.1
Long-context text generation
When a text generator analyzes the entire text produced so far to predict every next word, the cost of generating a document can become quadratic in its length. section 16.2
Figure 1.1 A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic, and exponential growth. The logarithmic curve is the shallowest, growing slowly, and the exponential curve is the fastest.
Compare quadratic growth visually with logarithmic, linear, quasilinear, and exponential growth. section 1.1
