Quadratic time complexity
Quadratic time complexity is an asymptotic running-time growth rate proportional to the square of input size, commonly denoted O(n²).
Grokking Algorithms, Second Edition
O(n2) is a quadratic time-complexity bound whose operation count grows with the square of the input size.
- How it is used
- Compares algorithm growth rates and describes the performance of sorting algorithms.
- How deep it goes
- Works through repeated scans and quicksort’s worst case, while deferring a fuller discussion of Big O constants.
- Examples
- Uses artist ranking by play count and quicksort’s call-stack levels as examples.
- What you can do after
- Evaluate algorithm growth by relating repeated scans or call-stack levels to operation counts.
Read how Grokking Algorithms, Second Edition explains quadratic time complexity →
Fabulous Adventures in Data Structures and Algorithms
Quadratic cost is a resource cost that grows proportionally to the square of an input's length.
- How it is used
- Measures how algorithmic resource costs scale as problem size increases.
- How deep it goes
- Defines doubling and tenfold effects, then diagnoses accidental quadratic implementations and contrasts an O(n) replacement.
- Examples
- Uses naïve string accumulation and whole-history text generation as concrete quadratic-cost examples.
- What you can do after
- Diagnose accidentally quadratic code and replace repeated string concatenation with StringBuilder.
Read how Fabulous Adventures in Data Structures and Algorithms explains quadratic time complexity →
How Large Language Models Work
Quadratic complexity is a computational growth rate proportional to the square of the input size, denoted O(n^2).
- How it is used
- Uses quadratic growth to explain computational limits on LLMs and increasingly difficult algorithms.
- How deep it goes
- Defines O(n^2) and connects it to LLM limits, while stopping short of formal algorithms or graduate-level complexity theory.
- Examples
- Contrasts quadratic complexity with routing, resource allocation, and prime factorization problems listed at cubic or exponential complexity.
- What you can do after
- Evaluate whether a problem’s required complexity may exceed an LLM’s ability to solve it efficiently and precisely.
Read how How Large Language Models Work explains quadratic time complexity →
Grokking Data Structures
Quadratic growth is growth proportional to the square of input size.
- How it is used
- Classifies algorithm running time or memory growth as input size increases.
- How deep it goes
- Defines O(n2), illustrates its growth with array pairs, and relates it to practical running times.
- Examples
- Uses array pairs, selection sort, mergesort, heapsort, and billion-element running-time estimates.
- What you can do after
- Evaluate whether an algorithm’s resource growth will remain manageable as its input becomes large.
Read how Grokking Data Structures explains quadratic time complexity →
Related concepts
- key-value cacheaddressed by · A key-value cache is a data structure that stores previously computed transformer attention keys and values for reuse during subsequent token generation.
- algorithmmeasures · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- quicksortmeasures · Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot and recursively sorts the resulting subranges.
- attentionused by · Attention is a neural-network mechanism that computes input-dependent weights to combine information according to its relevance to a computation.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.