Course contentsShow
← Machine Learning and Deep Learning
Lesson 1062 of 3,53824. The Transformer ArchitectureFree lesson

Attention Computational Complexity: O(n²d)

Analyze the quadratic complexity in sequence length and its implications for long sequences.

Attention Computational Complexity: O(n²d)

What you'll learn: You'll understand why attention mechanisms become expensive for long sequences and what the O(n²d) complexity means in practice.

The Cost of Comparing Everything

When you compute self-attention, you create an attention score matrix by comparing every token in a sequence with every other token. If your sequence has n tokens, this matrix is n × n in size. For each of these n² positions, you perform a dot product between vectors of dimension d (the model's hidden dimension).

This gives us O(n²d) computational complexity—quadratic in the sequence length.

Why This Matters for Long Sequences

Imagine processing a short sentence of 10 words versus a long document of 1,000 words:

  • 10 tokens: 10² = 100 comparisons
  • 1,000 tokens: 1,000² = 1,000,000 comparisons

The cost increased by 10,000× when the sequence grew by just 100×! This quadratic growth means:

  • Memory usage explodes (storing the n × n attention matrix)
  • Computation time scales poorly
  • Long documents (thousands of tokens) become impractical

Analogy: The Handshake Problem

Think of a party where everyone shakes hands with everyone else. With 10 people, you need 45 handshakes. With 100 people? 4,950 handshakes. With 1,000 people? Nearly 500,000 handshakes! This is why transformers struggle with very long sequences—they're doing the "handshake" of attention calculation for every token pair.

Key Takeaway: Attention's O(n²d) complexity means processing time and memory grow quadratically with sequence length, creating a bottleneck for long sequences that has driven research into efficient attention variants.