Quadratic time complexity

As explained in How Large Language Models Work

Quadratic complexity is a computational growth rate proportional to the square of the input size, denoted O(n^2).

Quadratic growth means that work increases roughly with the square of input size: an input of n items has complexity O(n^2). Doubling the input can therefore require about four times the work. section 7.4

This growth becomes a practical limit as inputs expand. The treatment uses quadratic complexity to explain why an LLM cannot efficiently solve problems proven to require more than O(n^2) work precisely. section 7.4

Figure 7.7 A Venn diagram of computational complexities (assuming \(P \neq NP\), a minor point for the nerds) relate to each other. The top arrows give examples of the kind of problem that a new complexity class lets you solve. The bottom arrows show where LLMs land in terms of their complexity.

Compare quadratic growth with other complexity classes and see where LLMs are placed in that hierarchy. section 7.4

How How Large Language Models Work covers it

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.

How it connects

Connects quadratic complexity with linear complexity, cubic complexity, exponential complexity, algorithmic complexity, and LLMs.

liveBookmanning.com

Read How Large Language Models Work on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionO(n2) is a quadratic time-complexity bound whose operation count grows with the square of the input size.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsQuadratic cost is a resource cost that grows proportionally to the square of an input's length.
• 

  liveBookmanning.com
  Grokking Data StructuresQuadratic growth is growth proportional to the square of input size.

Compare how 4 books explain 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.

This explainer was generated by Manning's knowledge graph from the text of How Large Language Models Work. The section links point to the parts of the book it draws on.