Big-O and token usage
Big-O describes how cost grows as the input grows, ignoring constants. For agents, the input is often tokens, and the cost is time, memory and money. This page covers the notation, then applies it to token usage.
The notation
Big-O is a set: writing f(n) = O(n²) means f is in the set of functions bounded by c·n². An O(n) algorithm is also O(n²), just not tightly; Θ is the precise statement.
Common growth classes
| Class | Name | Examples | Steps at n = 1,000 |
|---|---|---|---|
| O(1) | Constant | Array index, hash-map lookup (average), pushing onto a stack | 1 |
| O(log n) | Logarithmic | Binary search, balanced-tree lookup | ≈10 |
| O(n) | Linear | One pass over a list, linear search, summing | 1,000 |
| O(n log n) | Linearithmic | Merge sort, heap sort, average quicksort | ≈10,000 |
| O(n²) | Quadratic | Nested loops over the same list, bubble sort, all pairs | 1,000,000 |
| O(n³) | Cubic | Naive matrix multiplication, Floyd–Warshall | 10⁹ |
| O(2ⁿ) | Exponential | All subsets, naive recursive Fibonacci | ≈10³⁰¹ |
| O(n!) | Factorial | All orderings, brute-force travelling salesman | ≈10²⁵⁶⁷ |
Working it out
- Drop constants
O(3n + 5) = O(n). Constants matter in practice but not in the growth class.
- Keep the dominant term
O(n² + n log n + 100) = O(n²). The fastest-growing term wins for large n.
- Sequence adds
Doing A then B costs O(A + B). Two separate loops over n are O(n), not O(n²).
- Nesting multiplies
A loop of n around work of O(m) is O(n·m). The same list nested is O(n²).
- Keep separate inputs separate
Comparing a list of n with a list of m is O(n·m), not O(n²). Do not merge variables that can differ.
- Halving gives a log
If each step cuts the problem in half, there are log₂ n steps.
- Recursion: count calls × work per call
T(n) = 2T(n/2) + O(n) is O(n log n) (merge sort). T(n) = 2T(n−1) + O(1) is O(2ⁿ).
Which case, which resource
- Worst case
- The most work over all inputs of size n. The usual meaning of "the complexity".
- Average case
- Expected work over a distribution of inputs. Quicksort: O(n log n) average, O(n²) worst.
- Best case
- The least work. Rarely useful on its own: insertion sort is O(n) on sorted input.
- Amortized
- Average per operation over a sequence. Appending to a dynamic array is O(1) amortized though one append can copy O(n).
- Space
- Extra memory as n grows. Merge sort uses O(n) extra; heap sort O(1); recursion depth counts as space.
Divide and conquer: the master theorem
For T(n) = a·T(n/b) + f(n) (a ≥ 1 subproblems of size n/b, plus f(n) work to split and combine), compare f(n) with n^(log_b a):
| When | Then | Example |
|---|---|---|
| f(n) = O(n^(log_b a − ε)) | T(n) = Θ(n^(log_b a)) | T(n) = 8T(n/2) + n² → Θ(n³) |
| f(n) = Θ(n^(log_b a)) | T(n) = Θ(n^(log_b a) · log n) | T(n) = 2T(n/2) + n → Θ(n log n) |
| f(n) = Ω(n^(log_b a + ε)), regular | T(n) = Θ(f(n)) | T(n) = 2T(n/2) + n² → Θ(n²) |
Token usage: inside one model call
A token is a piece of text, a few characters of English on average, so token count grows linearly with text length. Here n is tokens in context, m tokens generated and d the model's width.
Self-attention compares every token with every earlier one. For typical lengths the linear O(n·d²) part dominates, so cost looks close to linear until contexts get long.
The cache stores keys and values for earlier tokens, so each new token attends to them once instead of reprocessing the prompt.
Each output token attends to the prompt and to the tokens generated before it.
Memory grows linearly with context, which is one reason context windows have a hard limit.
Providers charge per token, input and output at separate rates, so one call is linear in its tokens.
Token usage: across an agent's work
What usually dominates an agent's bill is not one call but how calls repeat. T is the number of turns and k the tokens each turn adds.
| Pattern | Growth | Why |
|---|---|---|
| One call | O(n) | Prompt plus answer, billed per token. |
| Agent loop that resends the full history | O(k·T²) | Turn t sends about t·k tokens, and k + 2k + … + T·k = k·T(T+1)/2. Doubling the turns roughly quadruples input tokens. |
| Same loop with prompt caching | Still O(k·T²) tokens, smaller constant | Cached prefix tokens are billed at a reduced rate, but every turn still reads the whole history. |
| Loop with summarizing or trimming to a cap C | O(T·C) | Context stops growing past C, so total input becomes linear in turns. |
| Retrieval: top-k chunks of size c | O(k·c) per question | Independent of corpus size, instead of putting all N documents in the prompt (O(N)). |
| Large tool outputs kept in history | Adds O(size × remaining turns) | A 10,000-token tool result early in a 20-turn loop is resent about 20 times. |
| Sampling s answers and voting | O(s·n) | Linear in samples. |
| Tree search: branching b, depth d | O(bᵈ) calls | Exponential; prune or cap the beam. |
Worked example: why long conversations get expensive
An agent adds 2,000 tokens per turn (user message, tool results, its reply) and resends the full history each turn. Total input tokens grow as k·T(T+1)/2. Capping the context at 20,000 tokens, by summarizing older turns, keeps growth linear.
| Turns (T) | Full history, O(T²) | Capped at 20,000, O(T) |
|---|---|---|
| 5 | 30,000 | 30,000 |
| 10 | 110,000 | 110,000 |
| 20 | 420,000 | 310,000 |
| 50 | 2,550,000 | 910,000 |
Ten times the turns (5 to 50) costs about 85 times the tokens with full history, and about 30 times with the cap. Below the cap the two are the same; past it, each extra turn costs a flat 20,000 instead of more every time.
Keeping token growth down
- Summarize or drop old turns once the context passes a budget; this turns O(T²) into O(T).
- Trim tool output before it enters the history: keep the lines that matter, not the whole log.
- Retrieve the few relevant chunks instead of pasting whole documents.
- Put stable content (instructions, tool definitions) first so prompt caching can reuse it.
- Cap output length where a short answer will do; output tokens usually cost more than input.
- Measure: attempts on this platform can record
tokens, so cost per scenario can be compared across agents and runs.