Quadratic time complexity
Quadratic time complexity is an asymptotic running-time growth rate proportional to the square of input size, typically expressed as O(n²).
Algorithms Every Programmer Should Know
A time complexity that grows quadratically with input size, or proportionally to n × m for two input lengths in the stated case.
- How it is used
- Measures how algorithm execution time grows as input size increases.
- How deep it goes
- Defines O(N²), links it to nested loops, and gives examples without deriving a formal bound.
- Examples
- Uses nested-loop sorting, participant-count estimates for Gale-Shapley, and ant-colony tour calculations.
- What you can do after
- Evaluate how increasing input size can raise algorithm runtime and compute demands.
Read how Algorithms Every Programmer Should Know explains quadratic time complexity →
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 →
Vibe Engineering
Quadratic time complexity is an algorithmic growth rate in which running time increases proportionally to the square of input size.
- How it is used
- Diagnoses hidden algorithmic costs that concurrency or optimization code can conceal.
- How deep it goes
- Traces O(N²) to repeated list scans and quantifies redundant comparisons, without developing formal complexity analysis.
- Examples
- Uses indexOf inside groupingBy, 10,000-account data, and benchmark results contrasting single-threaded, parallel, concurrent, and optimized methods.
- What you can do after
- Diagnose quadratic bottlenecks before trusting concurrency improvements or benchmark results.
Read how Vibe Engineering explains quadratic time complexity →
Building Specialized AI Systems
Quadratic complexity is computational growth proportional to the square of sequence length.
- How it is used
- Identifies why full self-attention becomes a bottleneck when processing very long contexts.
- How deep it goes
- Defines the square-length scaling and names mitigations, but does not derive the complexity mathematically.
- Examples
- Uses long-context attention, sparse and local patterns, RWKV, Mamba, RetNet, checkpointing, and mixed precision as examples.
- What you can do after
- Evaluate architecture and optimization choices when sequence length makes full self-attention costly.
Read how Building Specialized AI Systems 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 →
Also covered in
- Build an Advanced RAG Application (From Scratch)In early access (MEAP)
- Build a DeepSeek Model (From Scratch)In early access (MEAP)
What to know first
- performancePerformance is a measure of how effectively a person, process, model, or system achieves its objectives, including qualities such as output quality, speed, and resource efficiency.
- binary searchBinary search is an algorithm that repeatedly halves an ordered search interval to locate a target or determine its position or boundary.
- language modelA language model is a computational model that represents patterns in linguistic sequences to assign probabilities, predict, generate, or evaluate language.
- arrayAn array is an ordered collection of elements organized in one or more dimensions and accessible by position or index.
Related concepts
- key-value cacheaddressed by · A key-value cache stores attention keys and values computed for earlier tokens so they can be reused during subsequent autoregressive generation.
- time complexitykind of · Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
- algorithmmeasures · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
- attentionused by · Attention is a neural-network mechanism that computes input-dependent relevance weights to combine information from representations for a context-dependent computation.
- fusion-in-decoderaddressed by · Fusion-in-decoder is a retrieval-generation method that independently encodes multiple passages and fuses their representations in the decoder to generate an output.
- language modelused by · A language model is a computational model that represents patterns in linguistic sequences to assign probabilities, predict, generate, or evaluate language.
Questions about quadratic time complexity
What is quadratic time complexity?
Quadratic time complexity is an asymptotic running-time growth rate proportional to the square of input size, typically expressed as O(n²).
Which Manning books explain quadratic time complexity?
Algorithms Every Programmer Should Know, Grokking Algorithms, Second Edition, Vibe Engineering, Building Specialized AI Systems, Fabulous Adventures in Data Structures and Algorithms, How Large Language Models Work and Grokking Data Structures.
What should I know before learning quadratic time complexity?
Manning books that teach quadratic time complexity usually introduce performance, binary search, language model and array first.
What is quadratic time complexity a kind of?
Quadratic time complexity is a kind of time complexity. Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
What is quadratic time complexity also called?
Quadratic time complexity is also called quadratic complexity, O(n2), quadratic growth or quadratic scaling.
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.






