liveBook · Manning

Quadratic time complexity

Also called quadratic complexity, O(n2), quadratic growth, quadratic scaling

Quadratic time complexity is an asymptotic running-time growth rate proportional to the square of input size, typically expressed as O(n²).

How 7 Manning books explain it

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

What to know first

Related concepts

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.