Algorithmic Complexity Review

dot-skills Algorithmic Complexity (Big-O) Best Practices

Find, classify, and fix algorithmic complexity (Big-O) problems in code — language-agnostic. The 39 rules across 8 categories cover the patterns responsible for the vast majority of accidental quadratic, exponential, and N+1 blowups in production code: nested iteration, loop-invariant I/O, data-structure mismatch, recursion explosions, redundant computation, collection-building anti-patterns, search/sort selection, and space traps.

When to Apply

Use this skill when:

• Reviewing a pull request or function for performance regressions
• Asked "why is this slow?" or "can we make this faster?"
• Refactoring a hot path or a function that handles user-scaled input
• Reading code that contains: nested loops, .includes/.find/x in list inside iteration, ORM access in a loop, recursion without memoization, string/array building via += or spread, file/database I/O inside iteration
• Reviewing code that processes lists, trees, or streams whose size will grow

Workflow: Find, Classify, Fix

The skill is structured for a three-step workflow on any code under review:

1. Find — Scan for the Suspicion Patterns

Look for these structural signals first (highest hit rate):

2. Classify — Derive the Big-O

Compute complexity from the code structure:

When in doubt, ask: "As input doubles, does runtime roughly double (linear), quadruple (quadratic), or do something worse (exponential)?" That's the practical complexity class.

3. Fix — Apply the Pattern From the Matching Rule

Each reference file in references/ is a {category}-{slug}.md containing:

• WHY the pattern matters (the cascade effect)
• An Incorrect code example with the cost annotated
• A Correct example with the minimal diff
• When NOT to apply the fix (the rule has exceptions)

The minimal diff philosophy is intentional: the goal is for the agent to see exactly how few lines need to change to flip the complexity class.

Rule Categories by Priority

See `references/_sections.md` for the full ordering rationale.

Quick Reference

1. Nested Iteration Patterns (CRITICAL)

• `nested-explicit-quadratic-loops` — Replace pairwise loops with hash-based single passes
• `nested-includes-in-loop` — Avoid .includes() / .indexOf() inside a loop
• `nested-find-in-loop` — Pre-index lookups instead of .find() per iteration
• `nested-cartesian-comparison` — Group by key instead of cartesian comparison
• `nested-set-operations-on-arrays` — Use sets for intersection, union, difference
• `nested-substring-search-in-loop` — Tokenize once instead of re-scanning per pattern

2. Loop-Invariant I/O and N+1 Queries (CRITICAL)

• `io-n-plus-one-query` — Eliminate N+1 queries by fetching related data in one round trip
• `io-sequential-await-in-loop` — Run independent async operations in parallel
• `io-batch-instead-of-per-item` — Use batch endpoints instead of per-item calls
• `io-file-read-in-loop` — Read or stat files outside tight loops
• `io-missing-eager-load` — Eager-load ORM relations you will access

3. Data Structure Mismatch (HIGH)

• `ds-hashmap-for-keyed-access` — Store records keyed in a hashmap, not as parallel arrays
• `ds-heap-for-top-k` — Use a heap for top-k, not full sort + slice
• `ds-deque-for-front-operations` — Use a deque for front insertions and removals
• `ds-counter-for-histograms` — Use Counter / multiset for frequency counting
• `ds-sorted-structure-for-range-queries` — Use a sorted structure for range queries
• `ds-trie-for-prefix-search` — Use a trie for prefix search

4. Recursion Complexity (HIGH)

• `rec-memoize-overlapping-subproblems` — Memoize recursion with overlapping subproblems
• `rec-tabulate-bottom-up` — Tabulate bottom-up to eliminate recursion overhead
• `rec-iterative-for-deep-recursion` — Use an explicit stack instead of deep recursion
• `rec-prune-with-bounds` — Prune recursive search with bounds and constraints
• `rec-share-memo-across-top-level-calls` — Share memoization across top-level calls

5. Redundant Computation (MEDIUM-HIGH)

• `compute-hoist-loop-invariants` — Hoist loop-invariant computation outside the loop
• `compute-precompile-regex` — Pre-compile regex patterns
• `compute-cache-expensive-pure-results` — Cache expensive pure-function results
• `compute-cache-property-lookup` — Cache repeated property lookups in hot loops
• `compute-defer-or-short-circuit` — Defer or short-circuit work you might not need

6. Collection Building (MEDIUM)

• `build-avoid-quadratic-string-concat` — Build strings with joins or builders, not repeated concatenation
• `build-avoid-spread-in-reducer` — Push to a mutable accumulator instead of spreading
• `build-avoid-immutable-object-spread` — Use a plain object build phase, then freeze
• `build-presize-when-length-known` — Pre-size collections when the length is known

7. Search & Sort Selection (MEDIUM)

• `search-binary-search-on-sorted` — Use binary search on sorted data
• `search-sort-once-outside-loop` — Sort once outside the loop, not on every iteration
• `search-quickselect-not-full-sort` — Use quickselect for the k-th element, not full sort
• `search-build-index-once-amortize` — Build the index once when queries dominate

8. Space Complexity Traps (LOW-MEDIUM)

• `space-stream-dont-load` — Stream large inputs instead of loading them whole
• `space-generators-over-intermediate-lists` — Pipe through generators instead of materializing intermediate lists
• `space-shallow-not-deep-copy` — Use shallow copies (or no copy) instead of deep clones
• `space-release-retained-references` — Release references that prevent garbage collection

How to Use

1. Start with the Find signal table above to locate the most likely pattern. 2. Open the matching reference file for the WHY and the minimal-diff fix. 3. If you're classifying complexity from scratch, use the Classify table to derive Big-O from code structure. 4. When proposing a fix, quote the rule by file path so reviewers can verify the reasoning. 5. See `references/_sections.md` for category ordering rationale, and `assets/templates/_template.md` when adding new rules.

Reference Files

Related Skills

• bug-review — Multi-pass PR bug review (this skill is a focused complement for performance issues specifically)
• A language-specific best-practices skill (React, Python, Go) — covers idioms beyond Big-O; pair with this skill for performance-critical reviews

Algorithmic Complexity (Big-O)

Version 0.1.0 dot-skills May 2026

Note:

This document covers Algorithmic Complexity (Big-O) analysis and remediation.

It is mainly for agents and LLMs to follow when maintaining, generating, or

refactoring codebases. Humans may also find it useful, but guidance here is

optimized for automation and consistency by AI-assisted workflows.

---

Abstract

Language-agnostic algorithmic complexity review guide for AI agents. Contains 39 rules across 8 categories covering accidental quadratic patterns, N+1 I/O, data-structure mismatch, exponential recursion, redundant computation, collection-building anti-patterns, search/sort selection, and space-complexity traps. Each rule includes a minimal-diff incorrect/correct code example, an explanation of the cascade effect, and exceptions. Designed to help agents find, classify, and fix Big-O issues in code reviews, refactors, and performance investigations across Python, JavaScript/TypeScript, Java, Go, and similar languages.

---

Table of Contents

1. Nested Iteration Patterns — CRITICAL

• 1.1 Avoid `.includes()` / `.indexOf()` Inside a Loop — CRITICAL (O(n*m) to O(n+m) — typical 50-500× speedup)
• 1.2 Group by Key Instead of Cartesian Comparison — CRITICAL (O(n²) to O(n) — "find duplicates / similar pairs" is the canonical case)
• 1.3 Index Lookups Once Instead of `.find()` per Iteration — CRITICAL (O(n*m) to O(n+m) — application-side join speedup of 50-1000×)
• 1.4 Replace Pairwise Loops With Hash-Based Single Passes — CRITICAL (O(n²) to O(n) — 100× faster at n=10,000)
• 1.5 Tokenize Once Instead of Re-scanning a String per Pattern — CRITICAL (O(pL) to O(L+p) per document — across D docs, O(DpL) drops to O(D(L+p)))
• 1.6 Use Sets for Intersection, Union, and Difference — CRITICAL (O(n*m) to O(n+m) — typical 100× speedup on large lists)

2. Loop-Invariant I/O and N+1 Queries — CRITICAL

• 2.1 Declare Eager-Loading for ORM Relations You Will Access — CRITICAL (N+1 to 1-2 queries — same as N+1 but framed at the schema-traversal level)
• 2.2 Eliminate N+1 Queries by Fetching Related Data in One Round Trip — CRITICAL (N+1 round trips to 1-2 — typical 10-100× wall-clock speedup)
• 2.3 Read or Stat Files Outside Tight Loops — HIGH (O(n) syscalls eliminated — 10-100× speedup on disk-bound code)
• 2.4 Run Independent Async Operations in Parallel — CRITICAL (sum(latencies) to max(latencies) — typical 5-20× wall-clock speedup)
• 2.5 Use Batch Endpoints Instead of Per-Item Calls — CRITICAL (N calls to 1 batched call — 10-100× latency reduction)

3. Data Structure Mismatch — HIGH

• 3.1 Store Records Keyed in a Hashmap, Not as Parallel Arrays — HIGH (O(n) per lookup to O(1) — flips entire access patterns linear)
• 3.2 Use a Deque for Front Insertions and Removals — HIGH (O(n) per op to O(1) — flips queue/sliding-window code from quadratic to linear)
• 3.3 Use a Heap for Top-K, Not Full Sort + Slice — HIGH (O(n log n) to O(n log k) — 10-1000× speedup when k << n)
• 3.4 Use a Sorted Structure for Range Queries — HIGH (O(n) per range query to O(log n + k) — k = result size)
• 3.5 Use a Trie for Prefix Search — MEDIUM-HIGH (O(n*L) per query to O(L + k) — k = matches, L = query length)
• 3.6 Use Counter / Multiset for Frequency Counting — MEDIUM-HIGH (O(n²) to O(n) — and replaces 5-10 lines with one)

4. Recursion Complexity — HIGH

• 4.1 Memoize Recursion With Overlapping Subproblems — CRITICAL (O(2ⁿ) to O(n) — 1,000,000× faster at n=30)
• 4.2 Prune Recursive Search With Bounds and Constraints — HIGH (Worst-case exponential, practical 10-1000× speedup)
• 4.3 Share Memoization Across Top-Level Calls — HIGH (O(q*n) to O(q+n) for q queries — eliminates repeat exponential work)
• 4.4 Tabulate Bottom-Up to Eliminate Recursion Overhead — MEDIUM-HIGH (Same Big-O but 2-10× constant-factor speedup; eliminates stack-depth risk)
• 4.5 Use an Explicit Stack Instead of Deep Recursion — HIGH (Prevents stack overflow on n > ~1,000; modest perf win from removing frames)

5. Redundant Computation — MEDIUM-HIGH

• 5.1 Cache Expensive Pure-Function Results — MEDIUM-HIGH (Eliminates repeated heavy computation — common 10-100× speedups)
• 5.2 Cache Repeated Property Lookups in Hot Loops — MEDIUM (2-20× speedup when property access traverses multiple objects or proxies)
• 5.3 Compile Regex Patterns Once at Module Level — MEDIUM (5-50× per regex use — compilation typically dominates matching for short inputs)
• 5.4 Defer or Short-Circuit Work You Might Not Need — MEDIUM (Eliminates work entirely — speedup depends on hit rate but often 2-10×)
• 5.5 Hoist Loop-Invariant Computation Outside the Loop — MEDIUM-HIGH (Eliminates O(n) repeated work per loop body — 2-50× when invariant is heavy)

6. Collection Building — MEDIUM

• 6.1 Allocate Collections With the Known Final Length — LOW-MEDIUM (2-5× constant-factor speedup; avoids GC pressure from repeated reallocs)
• 6.2 Build Strings With Joins or Builders, Not Repeated Concatenation — HIGH (O(n²) to O(n) — orders of magnitude on large strings)
• 6.3 Push to a Mutable Accumulator Instead of Spreading — HIGH (O(n²) to O(n) — common 100-1000× speedup on JS reducers)
• 6.4 Use a Plain Object Build Phase, Then Freeze — MEDIUM-HIGH (O(n*k) to O(n) — k = property count of the growing object)

7. Search & Sort Selection — MEDIUM

• 7.1 Build the Index Once When Queries Dominate — MEDIUM-HIGH (O(q*n) to O(n + q) — break-even at q ≥ 1 for most index types)
• 7.2 Sort Once Outside the Loop, Not on Every Iteration — HIGH (O(n²·log n) to O(n·log n + n) — orders of magnitude on hot paths)
• 7.3 Use Binary Search on Sorted Data — MEDIUM-HIGH (O(n) per lookup to O(log n) — 1,000× speedup at n=1,000,000)
• 7.4 Use Quickselect for the K-th Element, Not Full Sort — MEDIUM (O(n log n) to O(n) average — useful when k is fixed and small)

8. Space Complexity Traps — LOW-MEDIUM

• 8.1 Pipe Through Generators Instead of Materializing Intermediate Lists — MEDIUM (O(n) intermediate storage to O(1) — also enables early exit)
• 8.2 Release References That Prevent Garbage Collection — LOW-MEDIUM (Prevents long-tail memory growth; GC pressure shows up as latency, not OOM)
• 8.3 Stream Large Inputs Instead of Loading Them Whole — HIGH (O(n) memory to O(1) — enables processing files larger than RAM)
• 8.4 Use Shallow Copies (or No Copy) Instead of Deep Clones — MEDIUM (O(size × depth) to O(1) or O(top-level) — 10-100× on nested structures)

---

References

1. https://wiki.python.org/moin/TimeComplexity 2. https://en.cppreference.com/w/cpp/algorithm 3. https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html 4. https://xlinux.nist.gov/dads/ 5. https://algs4.cs.princeton.edu/ 6. https://www.bigocheatsheet.com/ 7. https://use-the-index-luke.com/ 8. https://v8.dev/blog/elements-kinds 9. https://web.dev/articles/avoid-large-complex-layouts-and-layout-thrashing 10. https://docs.djangoproject.com/en/stable/ref/models/querysets/#select-related 11. https://github.com/graphql/dataloader

---

Source Files

This document was compiled from individual reference files. For detailed editing or extension:

{Title — mirror the frontmatter title}

{1-3 sentences explaining WHY the anti-pattern is bad. Focus on the cascade effect: what scales wrong, how the cost grows with input, why it's easy to miss at the call site. The model generalizes from understood reasoning, not from dictation — explain the mechanism, not just the rule.}

Incorrect ({short label, e.g., "linear scan per iteration"}):

```{language} {Production-realistic bad code — not a strawman} {// Comments quantify the cost: "10,000 × 50,000 = 500M comparisons"}

**Correct ({short label, e.g., "hash lookup"}):**

{Minimal-diff fix — should look like a small refactor of the incorrect version} {// Comments explain why the new version is cheaper}

**Alternative ({context}):**

{Optional. Include only when there's a genuinely different valid approach for a different
situation — e.g., "when the data is sorted" or "when keys are non-hashable".}

{Alternative implementation}

**When NOT to use this pattern:**

- {Specific exception with the input characteristics that make the rule wrong}
- {Another exception, ideally with measurable threshold ("when n < 30")}

Reference: [{Title of cited source}]({URL})

---

## Authoring Notes

When adding a new rule:

1. **Pick a prefix** from [`_sections.md`](../../references/_sections.md). The first tag MUST be the section prefix.
2. **Title in imperative form** — "Use", "Avoid", "Replace", "Cache", "Hoist".
3. **Quantify the impact** in `impactDescription`. Prefer Big-O class change (O(n²) to O(n))
   over vague "much faster". Add a concrete factor (e.g., "100× at n=10,000") when possible.
4. **Incorrect ≠ strawman** — write code that looks plausible, the kind of thing a competent
   engineer would write without thinking about complexity.
5. **Correct = minimal diff** — the goal is for the reader to see exactly which lines change.
6. **Add a "When NOT to use" section** for any rule with non-trivial exceptions. Rules without
   exceptions are rare; explicit exceptions make the model apply the rule with judgment.
7. **Reference an authoritative source** — primary docs (Python TimeComplexity, MDN, cppreference,
   NIST DADS), engineering blogs with benchmarks (V8 blog, web.dev), or canonical textbooks
   (CLRS, Sedgewick). Avoid tutorial sites and undated personal blogs.

Algorithmic Complexity Review

Language-agnostic Big-O review skill for AI agents. Helps find, classify, and fix algorithmic complexity issues in code — nested iteration, N+1 I/O, data-structure mismatch, recursion blowups, redundant computation, collection-building anti-patterns, search/sort selection, and space traps.

Overview

This skill is a distillation / code-quality Agent Skill. The agent's entry point is `SKILL.md`; the bulk of the content lives in references/ as 39 individually-loadable rule files organized by category prefix. The TOC navigation document `AGENTS.md` is auto-generated.

Structure

Getting Started

The skill is plain Markdown + JSON — no build step or runtime is needed to use it. The commands below operate on the parent dot-skills repo and the dev-skill plugin toolchain.

# In the parent dot-skills repo (one-time, if pnpm is the package manager)
pnpm install
pnpm build
pnpm validate

# Validate this skill specifically (preferred for iteration)
node {dev-skill-plugin}/scripts/validate-skill.js \
  skills/.experimental/algorithmic-complexity-review

# Rebuild the TOC after adding or editing rules
node {dev-skill-plugin}/scripts/build-agents-md.js \
  skills/.experimental/algorithmic-complexity-review

The skill is auto-loaded by Claude Code when its trigger description matches the user's intent. No installation step is required beyond having the skill present under skills/.

Creating a New Rule

1. Pick a category prefix from `references/_sections.md`. The first tag in the rule frontmatter must match this prefix. 2. Copy `assets/templates/_template.md` into references/{prefix}-{slug}.md. 3. Fill in the frontmatter (title, impact, impactDescription, tags), the WHY explanation, and the Incorrect / Correct code examples. 4. Add a "When NOT to use" section if the rule has non-trivial exceptions. 5. Cite an authoritative source at the bottom (Python TimeComplexity, MDN, NIST DADS, cppreference, V8 blog, CLRS, Sedgewick — see `metadata.json` for the canonical list). 6. Rebuild AGENTS.md and validate (see Scripts below).

Rule File Structure

Every rule file under references/ follows this layout:

---
title: {Action-Oriented Title}
impact: CRITICAL | HIGH | MEDIUM-HIGH | MEDIUM | LOW-MEDIUM | LOW
impactDescription: {Quantified impact, e.g., "O(n²) to O(n) — 100× at n=10,000"}
tags: {prefix}, {technique}, {tool-or-concept}
---

## {Title}

{1-3 sentences explaining WHY the anti-pattern matters — the cascade effect,
what scales wrong, why it hides at the call site.}

**Incorrect ({short label}):**

{Production-realistic bad code with cost annotations}

**Correct ({short label}):**

{Minimal-diff fix with benefit annotations}

**When NOT to use this pattern:**

- {Specific exception}

Reference: [{Title}]({URL})

The "Incorrect" example must be production-realistic (no strawman); the "Correct" example must be a minimal diff so the agent can see exactly which lines change.

File Naming Convention

Filenames must not collide across categories. Each prefix maps to exactly one category in _sections.md.

Impact Levels

Categories and individual rules are ordered by cascade severity (how much downstream work the anti-pattern blocks) × frequency in real code.

The 39 rules in this skill break down as:

Scripts

All scripts live in the dev-skill plugin toolchain, not in this skill. Replace {plugin} below with the active dev-skill plugin path (typically ~/.claude/plugins/cache/dot-claude/dev-skill/{version}).

Common invocations:

# Full validation
node {plugin}/scripts/validate-skill.js skills/.experimental/algorithmic-complexity-review

# Strict mode (treat warnings as errors)
node {plugin}/scripts/validate-skill.js skills/.experimental/algorithmic-complexity-review --strict

# Validate only _sections.md (during incremental authoring)
node {plugin}/scripts/validate-skill.js skills/.experimental/algorithmic-complexity-review --sections-only

# Rebuild AGENTS.md after editing rules
node {plugin}/scripts/build-agents-md.js skills/.experimental/algorithmic-complexity-review

Contributing

1. Open an issue describing the algorithmic pattern you want to add or correct, with at least one authoritative source (textbook, official docs, primary maintainer blog) backing the complexity claim. 2. Add the rule file under references/{prefix}-{slug}.md following Rule File Structure. 3. If the rule introduces a new category, add it to references/_sections.md first (with a one-sentence cascade-effect description) and run --sections-only validation. 4. Rebuild AGENTS.md, run full validation in strict mode, and ensure both pass with zero errors and zero warnings. 5. Open a PR. The reviewer will check teaching effectiveness, realism of the code examples, and accuracy of the impact claims against the cited source.

Discipline-aware review uses the rubric at {plugin}/templates/disciplines/distillation/RUBRIC.md. Run the skill-reviewer agent locally before requesting review.

Sections

This file defines all sections, their ordering, impact levels, and descriptions. The section ID (in parentheses) is the filename prefix used to group rules.

Categories are ordered by cascade severity — how catastrophically the anti-pattern scales with input size — multiplied by frequency in real code. The highest tiers contain patterns that turn linear-feeling code into quadratic, exponential, or N+1 disasters at production scale.

---

1. Nested Iteration Patterns (nested)

Impact: CRITICAL Description: Nested loops over collections produce O(n²), O(n³), or O(n*m) complexity — the most common production performance killer because it often hides behind innocuous-looking helpers (.includes, .find, .indexOf) called inside a loop. Doubling input size quadruples runtime; at 10× input, a quadratic algorithm runs 100× slower while the call site barely changed.

2. Loop-Invariant I/O and N+1 Queries (io)

Impact: CRITICAL Description: Performing a database query, network call, or file read inside a loop multiplies latency by collection size. A 50ms query repeated 200 times is 10 seconds — the database isn't slow, the access pattern is. Batching, eager loading, or hoisting the I/O outside the loop typically yields 10-100× wall-clock improvements with no algorithmic change.

3. Data Structure Mismatch (ds)

Impact: HIGH Description: Using the wrong container for the access pattern forces O(n) work where O(1) or O(log n) was available — linear search through arrays, repeated Array.prototype.includes on large lists, missing hash sets for membership tests, missing trees/heaps for ordered queries. The fix is a one-line container change that flips an entire loop's complexity class.

4. Recursion Complexity (rec)

Impact: HIGH Description: Unmemoized recursion with overlapping subproblems explodes exponentially — naive Fibonacci is O(2ⁿ) versus O(n) memoized, a 1,000,000× difference at n=30. Deep recursion also risks stack overflow on otherwise-correct algorithms. Memoization, tabulation, or iterative reformulation transforms exponential recurrences into polynomial ones.

5. Redundant Computation (compute)

Impact: MEDIUM-HIGH Description: Recomputing loop-invariant expressions, parsing the same regex repeatedly, calling pure functions with identical arguments in hot paths — work that gives the same answer every iteration. Hoisting invariants out of loops and caching expensive pure-function results are mechanical refactors that often eliminate 50-90% of CPU time.

6. Collection Building (build)

Impact: MEDIUM Description: Building strings or arrays by repeated concatenation creates accidental quadratic complexity — each s = s + part may copy the entire prefix. The same trap appears with immutable update patterns ({...obj, k: v} in a reducer, arr.concat(x) in a loop). Use builders, joins, or mutate-then-freeze patterns to keep construction linear.

7. Search & Sort Selection (search)

Impact: MEDIUM Description: Choosing the wrong search or sort strategy — linear scanning when the data is already sorted, re-sorting the same array on every iteration, using O(n log n) general sort when O(n) counting sort fits, or pre-sorting solely to do one lookup. Each is a localized fix but flips a hot loop's complexity class.

8. Space Complexity Traps (space)

Impact: LOW-MEDIUM Description: Unnecessary memory allocation — loading whole files instead of streaming, accumulating intermediate arrays before reducing, deep-cloning when a shallow reference suffices, retaining references that prevent garbage collection. Space and time interact: extra allocation creates GC pressure that shows up as latency spikes, not memory errors.

Use a Plain Object Build Phase, Then Freeze

{...acc, [k]: v} inside a reducer copies every existing key on every step. Building a 1,000-entry lookup table this way is ~500,000 copy operations, not 1,000. The fix is identical to the array spread case: mutate a plain object during construction (acc[k] = v; return acc), and if you need immutability afterwards, Object.freeze once at the end. The "no mutation" rule is about object identity stability for callers — it doesn't apply to the private accumulator inside reduce.

Incorrect (object spread per step — O(n²)):

const byId = items.reduce((acc, item) => ({
  ...acc,
  [item.id]: item,
}), {});
// 1,000 items × avg 500 keys copied = 500,000 ops; 10,000 items → 50M ops

Correct (mutate during build, freeze if needed):

const byId = items.reduce((acc, item) => {
  acc[item.id] = item;
  return acc;
}, {});
// 1,000 inserts, O(n) total

Alternative (built-in `Object.fromEntries`):

const byId = Object.fromEntries(items.map(item => [item.id, item]));
// O(n) — and clearer intent than a reduce

Alternative (`Map` when keys aren't statically known to be strings):

const byId = new Map(items.map(item => [item.id, item]));
// O(n), preserves insertion order, accepts any key type

When NOT to use this pattern:

• When you actually need a snapshot at each step (rare: typically only Redux-style time travel). Then the O(n²) is the price of the feature.
• For tiny objects (< 5 keys) — the constant factors don't show up; readability wins.

Reference: MDN — `Object.fromEntries`

Build Strings With Joins or Builders, Not Repeated Concatenation

Strings are immutable in most languages: s = s + part allocates a fresh string and copies both s and part into it. Inside a loop, each iteration copies the entire prefix accumulated so far — the work is 1 + 2 + 3 + … + n bytes, which is O(n²). Building a 1MB string this way moves a terabyte of memory. The fix is ''.join(parts) (Python), parts.join('') (JS), StringBuilder (Java), or strings.Builder (Go) — each appends to a growing buffer in amortized O(1), final concat is O(n).

CPython does have an optimization that sometimes in-places s = s + part for refcount-1 strings, but the optimization is contingent on internal refcount details and breaks under many normal conditions (aliasing, attribute access, augmented assignment in a class). Do not rely on it.

Incorrect (quadratic concatenation):

s = ""
for part in parts:                  # 10,000 parts × ~100 chars
    s = s + part
# Work: 100 + 200 + 300 + ... + 1,000,000 = 5 * 10^9 bytes copied
# ~5 seconds wall-clock for a 1MB result

Correct (`join` — linear total work):

s = "".join(parts)
# Single pass, ~1 million bytes copied total. Milliseconds.

Alternative (Java / Go — explicit builder):

StringBuilder sb = new StringBuilder();
for (String part : parts) sb.append(part);
String s = sb.toString();

var b strings.Builder
for _, part := range parts {
    b.WriteString(part)
}
s := b.String()

When NOT to use this pattern:

• When you genuinely only concatenate two or three strings — single + is clearer and the runtime is fine.
• When you're streaming output (writing to a file or network) — write each chunk directly, don't accumulate into a string at all.

Reference: Python performance tips — string concatenation

Push to a Mutable Accumulator Instead of Spreading

acc => [...acc, x] looks like a clean append but is O(|acc|) — it allocates a new array and copies every prior element on each step. Used as a reduce callback over n items, the total work is O(n²). The same trap appears with acc.concat(x). The fix is to mutate the accumulator (acc.push(x); return acc) — the reducer's accumulator is internal to the reduce; there's no aliasing problem and no actual immutability gain. Linters that flag mutation in reducers are wrong about this specific pattern.

Incorrect (spread on every step — O(n²)):

const doubled = numbers.reduce((acc, n) => [...acc, n * 2], []);
// 10,000 numbers → 50,000,000 copy operations (~seconds in V8)

Correct (mutate the accumulator — O(n)):

const doubled = numbers.reduce((acc, n) => {
  acc.push(n * 2);
  return acc;
}, []);
// 10,000 operations total

Alternative (just use `map` when the shape is "transform each"):

const doubled = numbers.map(n => n * 2);
// Same O(n) but clearer intent; the reduce was overkill here

Alternative (filter+map composition):

// Avoid: spread builds a fresh array every step
const result = items.reduce(
  (acc, x) => x.active ? [...acc, transform(x)] : acc,
  []
);

// Better: chain
const result = items.filter(x => x.active).map(transform);

When NOT to use this pattern:

• When the reducer is intentionally producing new immutable snapshots (e.g., Redux), and each step's result is held by something else (time-travel debugging). Then the cost is paying for a feature you want.

Reference: V8 blog — array spread copies elements

Allocate Collections With the Known Final Length

Dynamic arrays and hashmaps grow by doubling capacity when full — each growth allocates a new backing array and copies existing entries. The amortized cost is O(1) per insert, but the constant factor includes several reallocations and the GC pressure of orphaned old buffers. When the final size is known up-front (you're transforming a list of known length, parsing a known number of records), pre-sizing the container eliminates the reallocations and the GC work, typically saving 2-5× on hot paths. In Python this matters most for dict; in Java for ArrayList/HashMap; in Go for make([]T, 0, n).

Incorrect (default capacity — multiple grow-and-copy cycles):

// Go: default capacity grows from 1 → 2 → 4 → 8 → 16 → ... reallocating each time
results := []int{}
for _, x := range data {       // len(data) == 100_000
    results = append(results, transform(x))
}
// ~17 reallocations + copies of growing backing arrays

Correct (pre-allocate with known capacity):

results := make([]int, 0, len(data))   // capacity = len(data), length = 0
for _, x := range data {
    results = append(results, transform(x))
}
// Zero reallocations

Alternative (Python `dict` — comprehension is faster than per-key assignment):

# Slower: explicit loop pays bytecode dispatch per insert
result = {}
for k, v in pairs:
    result[k] = transform(v)

# Faster: comprehension uses a tight bytecode loop (BUILD_MAP / MAP_ADD)
# and avoids the per-iteration STORE_NAME of the dict. Note: CPython does
# NOT pre-size from generator length, but the loop overhead is lower.
result = {k: transform(v) for k, v in pairs}

Alternative (Java — pre-size HashMap to avoid rehashing):

// HashMap default capacity is 16, rehashes at 75% load → grows for any data
Map<Integer, User> map = new HashMap<>(items.size() * 4 / 3 + 1);
for (User u : items) map.put(u.id, u);

When NOT to use this pattern:

• When the final size is not known and you'd have to estimate badly — the dynamic growth is exactly designed for this case.
• When the data is small (< 100 items) — the savings are immeasurable.

Reference: Go blog — `slices` and `append` semantics

Cache Expensive Pure-Function Results

Pure functions (deterministic output, no side effects) are safe to memoize — call them once per distinct argument set, cache the result. The pattern applies broadly: date parsing (new Date(s) against the same string), JSON parsing of constants, cryptographic digests, expensive normalizations (unicode.normalize, path.resolve), feature-flag lookups, ML embeddings. Inside hot loops these accumulate fast; one datetime.strptime is microseconds, but a million of them is a second of CPU you spend instead of doing useful work. Distinct from `rec-share-memo-across-top-level-calls`, which addresses recursion — this rule covers non-recursive computation that happens to be repeated.

Incorrect (re-parse the same constants — O(n) repeat work):

def is_in_business_hours(ts):
    open_time = datetime.strptime("09:00", "%H:%M").time()    # parse every call
    close_time = datetime.strptime("17:00", "%H:%M").time()   # parse every call
    return open_time <= ts.time() <= close_time

for event in events:                # 1,000,000 events
    if is_in_business_hours(event.timestamp):
        ...
# 2,000,000 redundant strptime calls

Correct (parse once, reference the cached value):

_BUSINESS_OPEN = datetime.strptime("09:00", "%H:%M").time()
_BUSINESS_CLOSE = datetime.strptime("17:00", "%H:%M").time()

def is_in_business_hours(ts):
    return _BUSINESS_OPEN <= ts.time() <= _BUSINESS_CLOSE

Alternative (`lru_cache` for argument-keyed memoization):

from functools import lru_cache

@lru_cache(maxsize=1024)
def parse_locale(locale_str):
    # Expensive: ICU lookup, normalization, fallback chain
    return _load_locale_data(locale_str)

# Hot path: called with ~50 distinct locales over millions of requests
# → 50 expensive parses total, rest are O(1) cache hits

When NOT to use this pattern:

• When the function depends on hidden state (clock, RNG, mutable globals) — cached results lie. Either make the dependencies explicit arguments or skip the cache.
• When inputs are nearly always distinct — the cache fills with single-use entries and just wastes memory.

Reference: `functools.lru_cache` — Python's standard memoization decorator

Cache Repeated Property Lookups in Hot Loops

Property lookups look free but aren't: each obj.a.b.c traverses three properties, and on objects with prototype chains, getters, or Proxy interceptors, every dereference can run code. The DOM is the worst offender — element.offsetWidth triggers layout, element.style.color triggers style resolution. Inside a tight loop, repeated identical accesses pile up. Cache the deep reference in a local once, then index off it. Modern JS engines (V8 inline caches) handle simple paths well, but Proxy / getter / DOM properties bypass these optimizations.

Incorrect (DOM property thrash — layout per iteration):

for (let i = 0; i < items.length; i++) {           // .length read each iter
  const w = container.offsetWidth;                 // FORCES layout each iter
  items[i].style.width = (w / items.length) + 'px';
}
// 1,000 items → ~1,000 forced layouts (typically 100+ ms total)

Correct (hoist + cache):

const n = items.length;
const w = container.offsetWidth;                   // one layout
const cellW = (w / n) + 'px';
for (let i = 0; i < n; i++) {
  items[i].style.width = cellW;
}

Alternative (deeply nested object access):

// Avoid: repeated chain access — even with V8 inline caching, four lookups per iter
for (const row of rows) {
  if (row.user.profile.preferences.locale === 'en-US') { ... }
}

// Better: destructure once, reference the local
const target = 'en-US';
for (const row of rows) {
  const { locale } = row.user.profile.preferences;
  if (locale === target) { ... }
}

When NOT to use this pattern:

• When the property may change between iterations (loop body mutates it) — caching introduces a stale-read bug.
• For trivial scalar properties on plain objects in non-hot code — V8/JSC inline caches handle these for free.

Reference: Google web.dev — avoiding forced synchronous layouts (FSL)

Defer or Short-Circuit Work You Might Not Need

The cheapest computation is the one you never run. Eagerly computing values "in case the caller needs them" pays for work that will be thrown away when the caller takes the early-exit path. Two complementary patterns:

• Short-circuit: order boolean conditions cheap-first so expensive checks are skipped when an early condition fails. cheap_check(x) and expensive_check(x) is dramatically faster than expensive_check(x) and cheap_check(x) on the false-majority case.
• Defer / lazy: generate values on demand (generators, lazy properties), so a caller that only needs the first match doesn't pay for the rest of the collection.

Incorrect (eager — compute everything up front):

def find_first_match(items, pattern):
    matches = [item for item in items if pattern.match(item.text)]   # O(n)
    return matches[0] if matches else None
# 1,000,000 items, match on item 5 → still scans all 1,000,000

Correct (lazy — stop at the first match):

def find_first_match(items, pattern):
    return next((item for item in items if pattern.match(item.text)), None)
# Stops the moment the first matching item is yielded — typically O(position)

Alternative (predicate ordering — cheap before expensive):

# Bad: expensive regex first, even though most items fail the cheap check
matches = [x for x in items if EXPENSIVE_RE.match(x.body) and x.score > 0]

# Good: cheap numeric check filters first; regex only runs on survivors
matches = [x for x in items if x.score > 0 and EXPENSIVE_RE.match(x.body)]

When NOT to use this pattern:

• When the values will all be consumed anyway — laziness adds bookkeeping for no benefit.
• When the lazy computation has side effects (DB queries, side-effecting iteration) that callers may not realize are deferred. Make it explicit.

Reference: Python iterators and generators — lazy evaluation

Hoist Loop-Invariant Computation Outside the Loop

An expression whose value doesn't depend on the loop variable should be computed once before the loop, not n times inside it. Compilers do this automatically for simple cases (for i in range(0, len(xs)) typically caches len(xs)), but interpreted languages on dynamic expressions often don't — and humans frequently nest expensive operations (regex compilation, list len() on changing lists, function-property lookups, environment-variable reads) inside loops without realizing the cost. The fix is mechanical: identify expressions in the loop body whose inputs are all loop-invariant, lift them above the loop, reference the local in the body.

Incorrect (recomputes invariants per iteration):

# Bad: re.compile, str.upper on constant string, environment lookup
import os, re
for line in lines:
    pattern = re.compile(r'^\s*(WARN|ERROR)\s+(.*)$')   # compile each iter
    if pattern.match(line.upper()) and os.environ.get('STRICT') == '1':
        ...
# 100,000 lines × ~10μs regex compile = 1 second of compilation alone

Correct (compute once, reference inside):

import os, re
pattern = re.compile(r'^\s*(WARN|ERROR)\s+(.*)$')
strict = os.environ.get('STRICT') == '1'
for line in lines:
    if pattern.match(line.upper()) and strict:
        ...
# Compile + env lookup happen once

Alternative (loop-invariant DOM in browser code):

// Avoid: each .className access does a string allocation and DOM read
for (const el of nodes) {
  if (el.className.includes('active')) { ... }   // DOM property read
}

// Better: convert to a Set once, drop DOM lookups inside the loop
const active = new Set(document.querySelectorAll('.active'));
for (const el of nodes) {
  if (active.has(el)) { ... }
}

When NOT to use this pattern:

• When the expression appears to be invariant but actually mutates (subtle aliasing). Verify with a test.
• When hoisting hurts readability and the loop is cold — premature optimization. Profile before refactoring obscure code.

Reference: Wikipedia — loop-invariant code motion (compiler optimization)

Compile Regex Patterns Once at Module Level

Regex compilation walks the pattern, parses it, builds an NFA/DFA, and allocates. Matching is the cheap part — for short inputs, matching against a precompiled regex can be 10-50× faster than the equivalent re.match(r'...', s) call. Python's re module caches the last ~512 patterns automatically, so the impact is smaller there than people fear, but you still pay a dict lookup; in JavaScript, new RegExp(pattern) in a hot path has no module-level cache and recompiles every time. The portable rule: compile any regex used more than once into a module-level constant.

Incorrect (recompile per call):

function isEmail(s, locale) {
  // Pattern built from a string — V8 cannot cache this across calls
  const pattern = `^[^@]+@[^@]+\\.[^@]+\\.${locale}$`;
  return new RegExp(pattern).test(s);                    // compile every call
}
// 1,000,000 validations → 1,000,000 compilations

Correct (compile once at module level, or cache by locale):

const EMAIL_RE_BY_LOCALE = new Map();

function isEmail(s, locale) {
  let re = EMAIL_RE_BY_LOCALE.get(locale);
  if (!re) {
    re = new RegExp(`^[^@]+@[^@]+\\.[^@]+\\.${locale}$`);
    EMAIL_RE_BY_LOCALE.set(locale, re);
  }
  return re.test(s);
}
// N distinct locales → N compilations total, regardless of call count

Alternative (Python — module-level constant or `re.compile`):

import re
_EMAIL_RE = re.compile(r'^[^@]+@[^@]+\.[^@]+$')

def is_email(s):
    return bool(_EMAIL_RE.match(s))

When NOT to use this pattern:

• When the pattern is genuinely dynamic per call (built from user input) — you must compile each time. Cache compiled patterns in a dict if the set of dynamic patterns is small.
• For one-off matches outside any loop — inline regex is clearer and the cost is negligible.

Reference: Python `re` module — performance considerations

Use Counter / Multiset for Frequency Counting

Frequency counting ("how many times does each value appear?") and the related most-common / top-k questions are common enough that the standard library has a primitive for them: collections.Counter (Python), MultiSet in Apache Commons (Java), lodash.countBy / Map (JS). The manual implementation — initialize a dict, check if key not in counts, increment — works but is verbose, easy to get wrong (forgetting the default), and slower than the C-optimized Counter. The Counter primitive also exposes most_common(k), which uses a bounded heap internally and is the right structure for top-k frequency questions.

Incorrect (manual increment — O(n) but error-prone, no top-k helper):

counts = {}
for word in words:
    if word in counts:
        counts[word] += 1
    else:
        counts[word] = 1

# Now find the top 10 words — manual sort, full O(n log n):
top_10 = sorted(counts.items(), key=lambda kv: -kv[1])[:10]

Correct (`Counter`):

from collections import Counter
counts = Counter(words)            # O(n), C-optimized
top_10 = counts.most_common(10)    # O(n log 10) via internal heap

Alternative (JavaScript):

// Map preserves insertion order, supports any key type
const counts = new Map();
for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);

When NOT to use this pattern:

• When you need a sliding-window count over a stream — a Counter rebuilt per window is wasteful; maintain it incrementally with add/remove deltas.

Reference: Python `collections.Counter` — frequency dictionary subclass

Use a Deque for Front Insertions and Removals

list.pop(0), list.insert(0, x), Array.prototype.shift, and Array.prototype.unshift all run in O(n) because the underlying contiguous array must memmove every element one slot. Used inside a loop — say, a BFS dequeue or a sliding-window slide — they turn an O(n) algorithm into O(n²). A double-ended queue (collections.deque in Python, ArrayDeque in Java, LinkedList or a ring buffer in JS) supports both ends in O(1).

Incorrect (list as a queue — O(n²) for n dequeues):

queue = list(initial_items)
while queue:
    item = queue.pop(0)            # O(n) shift of remaining elements
    for child in children(item):
        queue.append(child)
# n items dequeued → O(n²) total

Correct (deque — O(n) total):

from collections import deque
queue = deque(initial_items)
while queue:
    item = queue.popleft()         # O(1)
    for child in children(item):
        queue.append(child)

Alternative (sliding window over a stream):

from collections import deque
window = deque(maxlen=K)           # auto-evicts the oldest on append when full
for value in stream:
    window.append(value)           # O(1) — old element drops out for free
    process(window)

When NOT to use this pattern:

• When the queue is provably tiny (≲ ~30 items) and bounded — the constant factors of deque and list are similar; choose for readability.
• In JavaScript, when you need random access by index frequently — a deque library may not match Array's indexed access; consider a ring buffer or two stacks if appropriate.

Reference: Python `collections.deque` — O(1) appends and pops from either end

Store Records Keyed in a Hashmap, Not as Parallel Arrays

If callers will retrieve records by an ID, store them in a Map/dict keyed by that ID. The mistake is keeping the result of an API call or query as a flat array and reaching for .find every time you need one entry — each lookup is O(n), so any code that touches the collection more than once silently scales as O(n²). The fix is a one-time O(n) reshape after the data arrives. This is the same idea as `nested-find-in-loop`, but framed as a data-modeling decision at the boundary where the collection enters the system, not a refactor at the loop.

Incorrect (array storage, repeated find — O(n) per access):

const users: User[] = await api.getUsers();

function getName(id: string) {
  return users.find(u => u.id === id)?.name;   // O(n) every call
}

// 1,000 page renders × find on 50,000 users = 50,000,000 comparisons

Correct (hashmap storage — O(1) per access):

const userArray = await api.getUsers();
const users = new Map(userArray.map(u => [u.id, u]));   // O(n) once

function getName(id: string) {
  return users.get(id)?.name;                  // O(1)
}

Alternative (when iteration order matters):

// JS Map preserves insertion order — supports both random access and ordered iteration
const users = new Map(userArray.map(u => [u.id, u]));
for (const user of users.values()) { ... }    // ordered iteration
users.get(id);                                  // O(1) random access

When NOT to use this pattern:

• When the collection is iterated once and never looked up again — the hashmap conversion is wasted work.
• When IDs are not stable (e.g., transient queue messages) — a hashmap of moving keys still works but offers no real advantage.

Reference: JavaScript `Map` — ECMAScript spec mandates sublinear average access (amortized O(1))

Use a Heap for Top-K, Not Full Sort + Slice

"Find the top 10 scores from a million entries" doesn't need a full sort. A sort is O(n log n) and produces a fully ordered list you immediately throw 999,990 elements of. A bounded min-heap of size k visits each element once, pushing if it's larger than the current minimum — O(n log k) total, which is dramatically faster when k is small relative to n. The Python heapq.nlargest, JS priority-queue libraries, and Java PriorityQueue all implement this directly.

Incorrect (sort everything then take k — O(n log n)):

top_10 = sorted(scores, reverse=True)[:10]
# 1,000,000 scores: full sort touches every element, O(n log n) ≈ 20M ops

Correct (bounded heap — O(n log k)):

import heapq
top_10 = heapq.nlargest(10, scores)
# 1,000,000 scores: O(n log 10) ≈ 3.3M ops, plus much less memory churn

Alternative (when items have a key function):

top_10_users = heapq.nlargest(10, users, key=lambda u: u.score)

When NOT to use this pattern:

• When k is close to n (e.g., top 90% of 100 items) — the heap saves nothing; a full sort is clearer.
• When you also need the remaining items in some order — you'll sort anyway; combine the two passes.

Reference: Python `heapq.nlargest` — runs in O(n log k)

Use a Sorted Structure for Range Queries

"Give me every event between t₁ and t₂" against an unsorted list forces a full scan — O(n) per query. A balanced binary search tree (TreeMap in Java, std::map in C++, sortedcontainers.SortedDict in Python) finds the lower bound in O(log n) and walks forward until t₂ — O(log n + k) where k is the result count. The same applies to "smallest item ≥ x," "largest ≤ x," and "k-th order statistic" — questions that are answered in microseconds against a sorted structure and seconds against a list.

Incorrect (linear scan per query — O(n) each):

events = [...]   # 500,000 events, unsorted by timestamp

def events_in_range(t1, t2):
    return [e for e in events if t1 <= e.timestamp <= t2]   # O(n)

# 1,000 queries × 500,000 = 500,000,000 comparisons

Correct (sorted structure — O(log n + k) per query):

from sortedcontainers import SortedDict
events_by_ts = SortedDict()
for e in events:
    events_by_ts[e.timestamp] = e             # O(n log n) once

def events_in_range(t1, t2):
    return list(events_by_ts.irange(t1, t2))  # O(log n + k)

Alternative (when range queries are rare but inserts are frequent):

# If reads are bursty after a load phase, sort once and use bisect
import bisect
events.sort(key=lambda e: e.timestamp)
timestamps = [e.timestamp for e in events]

def events_in_range(t1, t2):
    lo = bisect.bisect_left(timestamps, t1)
    hi = bisect.bisect_right(timestamps, t2)
    return events[lo:hi]                       # O(log n + k)

When NOT to use this pattern:

• When ranges almost always cover most of the data — the structural advantage shrinks; a plain sorted list with bisect is simpler.
• When you also need approximate-membership queries on a stream — consider a Bloom filter or count-min sketch instead.

Reference: `sortedcontainers.SortedDict` — exposes `irange` and `irange_key` in O(log n + k)

Use a Trie for Prefix Search

Autocomplete and prefix-match queries against a list of strings are O(n*L) — for every one of n entries, check whether its first L characters match. A trie indexes by character, so a prefix query walks L levels down the tree and then enumerates only matching leaves — O(L + k) where k is the result count. For a dictionary of 100,000 words, prefix lookup is microseconds against a trie versus tens of milliseconds against a list. The same structure also accelerates "is X a prefix of any stored word?" — a single tree walk gives a yes/no answer.

*Incorrect (linear scan per query — O(nL)):**

def autocomplete(prefix, words):
    return [w for w in words if w.startswith(prefix)]
# 100,000 words × ~8-char prefix check = ~800K character comparisons per keystroke

Correct (trie — O(L + k) per query):

# Tiny trie sketch — production: use `pygtrie`, `marisa-trie`, or build with classes
trie = {}
for word in words:
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})
    node['$'] = word                    # mark word boundary

def autocomplete(prefix, trie):
    node = trie
    for ch in prefix:
        if ch not in node:
            return []
        node = node[ch]
    return _collect(node)               # DFS from current node — O(k)

def _collect(node):
    out = []
    if '$' in node: out.append(node['$'])
    for ch, child in node.items():
        if ch != '$': out.extend(_collect(child))
    return out

Alternative (sorted array + binary search for static dictionaries):

import bisect
words.sort()
def autocomplete(prefix):
    lo = bisect.bisect_left(words, prefix)
    out = []
    while lo < len(words) and words[lo].startswith(prefix):
        out.append(words[lo]); lo += 1
    return out
# O(log n + k) per query — simpler than a trie, similar perf for static data

When NOT to use this pattern:

• When the dictionary is small (≲ 1,000 words) and queries are infrequent — the constant factors dominate.
• When you also need fuzzy matching — reach for BK-trees, Levenshtein automata, or n-gram indexes instead.

Reference: Trie (NIST DADS) — prefix-tree data structure

Use Batch Endpoints Instead of Per-Item Calls

Most well-designed APIs expose batch variants (/users?ids=1,2,3, INSERT ... VALUES (...), (...), (...), mset, multiGet) precisely because individual calls amortize poorly: each one pays TLS, auth, framing, and routing overhead regardless of payload size. A single batched call typically handles 100-1000 items for less wall-clock time than two individual calls, because the cost is dominated by round trips, not per-item work. Reach for the batch variant whenever the loop body is "send one thing over the wire" and the call sites are inside the same logical operation.

Incorrect (per-item calls — N round trips):

# Redis client — one round trip per key
for user_id in user_ids:                            # 500 ids
    pipe.append(redis.get(f"user:{user_id}"))       # 500 round trips

Correct (single batch call):

keys = [f"user:{uid}" for uid in user_ids]
values = redis.mget(keys)                           # 1 round trip

Alternative (auto-batching with DataLoader / accumulator):

// GraphQL / Node — DataLoader collects calls in one tick, batches them
import DataLoader from 'dataloader';
const userLoader = new DataLoader(ids => fetchUsersByIds(ids));

// Each call looks individual but is auto-batched per event-loop tick
const u1 = await userLoader.load(1);
const u2 = await userLoader.load(2);
// Underlying call: fetchUsersByIds([1, 2]) — one round trip

When NOT to use this pattern:

• When the API has a hard batch-size limit and N >> limit — chunk into batches of limit and Promise.all the chunks; see `io-sequential-await-in-loop`.
• When per-item operations need independent error handling — a partial-failure batch API helps; otherwise consider Promise.allSettled over individual calls.

Reference: graphql/dataloader — batching and caching

Read or Stat Files Outside Tight Loops

Every open(), read(), stat(), exists() is a kernel transition. On a hot path, syscalls dominate runtime even when the data is in OS page cache — the user→kernel→user trip costs microseconds that add up to seconds at N=100k. The right pattern is one of: (1) read the file once outside the loop, (2) bulk-walk the directory with a single os.scandir / fs.readdir, or (3) memoize the result if it can't change during the run. The wrong pattern is "re-check the config file" or "open this template" inside each iteration of a request handler.

Incorrect (re-read per iteration — N syscalls):

# Render each row through the same template — file read N times
for row in rows:                                # 50,000 rows
    with open('template.txt') as f:             # syscall per row
        template = f.read()
    print(template.format(**row))

Correct (hoist the read — 1 syscall):

with open('template.txt') as f:                 # once
    template = f.read()
for row in rows:
    print(template.format(**row))

Alternative (caching when reads must respect mtime):

from functools import lru_cache
import os

@lru_cache(maxsize=128)
def _load_template(path, mtime):
    with open(path) as f:
        return f.read()

def load_template(path):
    return _load_template(path, os.stat(path).st_mtime)
# First load: 2 syscalls (stat + read). Subsequent: 1 syscall (stat only).

When NOT to use this pattern:

• When the file is genuinely expected to change during the loop (log tail, control file). Then the per-iteration cost is intrinsic — consider inotify/FSEvents instead of polling.

Reference: Python `os.scandir` is faster than `listdir`+`stat` because it avoids the per-entry syscall

Declare Eager-Loading for ORM Relations You Will Access

Most ORMs lazy-load relations: accessing order.customer.address.city issues a query the first time each . is dereferenced. Inside a loop, this hides N+1 (then N+1+N, then N+1+N+M…) behind property accesses. Declare upfront which relations the code path needs (select_related, prefetch_related, Include, JOIN FETCH) so the ORM emits one or two joined queries instead of a fan-out. This is the same problem as `io-n-plus-one-query` but framed at the schema-graph level: you must tell the ORM how deep you intend to traverse.

Incorrect (lazy chains issue queries on every dot):

# Django — 1 + N + N queries for a 2-deep traversal
orders = Order.objects.all()
for order in orders:
    print(order.customer.name)                  # query 1
    print(order.customer.address.city)          # query 2
# 200 orders → 401 queries

Correct (declare the traversal upfront):

orders = Order.objects.select_related('customer__address').all()
for order in orders:
    print(order.customer.name)                  # already joined
    print(order.customer.address.city)          # already joined
# 200 orders → 1 query

Alternative (collection relations use prefetch):

# Many line items per order — JOIN would explode rows; use a 2-query plan
orders = (
    Order.objects
        .select_related('customer')
        .prefetch_related('line_items__product')
)

Detection: The Django debug toolbar (or django.db.connection.queries) shows query counts per request. Any controller whose query count scales with rendered items is missing an eager load. Sequelize has logging, Active Record has ActiveSupport::Notifications, Hibernate has SQL logging.

Reference: Hibernate — `JOIN FETCH` for eager loading

Eliminate N+1 Queries by Fetching Related Data in One Round Trip

The N+1 problem: 1 query to fetch a list, then N queries to fetch each item's related data. Each extra round trip pays the network/parsing cost regardless of how trivial the SQL is. At 200 items and 5ms per query, that's a full second of latency that vanishes if you fetch all related rows in a single query with IN (...) or a join. The pattern is universal across ORMs (Active Record, Django, Sequelize, Hibernate, SQLAlchemy) because the lazy-loading default makes the bug invisible at the call site.

Incorrect (N+1 — one query per item):

# Django — issues 1 + len(orders) queries
orders = Order.objects.filter(status='paid')           # 1 query
for order in orders:
    print(order.customer.name)                          # 1 query each
# 200 orders → 201 queries → 201 round trips

Correct (eager load related rows in one query):

orders = (
    Order.objects.filter(status='paid')
        .select_related('customer')                     # JOIN customer in
)
for order in orders:
    print(order.customer.name)                          # already loaded
# 200 orders → 1 query

Alternative (when relation is many-to-many or reverse FK):

# Use prefetch_related for collections — 2 queries total, joined in Python
orders = Order.objects.filter(status='paid').prefetch_related('line_items')

Detection: Enable query logging in development. Any view that issues queries proportional to the number of items rendered has an N+1 — see the framework's debug toolbar or django.db.connection.queries.

Reference: Django — `select_related` and `prefetch_related`

Run Independent Async Operations in Parallel

for (const x of xs) { await fetch(x) } runs the requests strictly one after another — total latency is the sum of all request latencies. When the operations don't depend on each other, this serial execution is purely wasteful: every request after the first is waiting on the previous response for no logical reason. Promise.all (JS) / asyncio.gather (Python) / errgroup (Go) issue them concurrently, so total latency collapses to roughly the slowest single request. The complexity class doesn't change but the wall-clock improvement is typically the most visible perf win in any service that fans out to external APIs.

Incorrect (sequential — Σ latencies):

const results = [];
for (const id of userIds) {
  results.push(await fetchUser(id));    // each await blocks the next
}
// 50 users × 80ms = 4 seconds

Correct (parallel — max latency):

const results = await Promise.all(
  userIds.map(id => fetchUser(id))      // fires all at once
);
// 50 users in ~80ms (slowest single request)

Alternative (bounded concurrency for rate-limited APIs):

import pLimit from 'p-limit';
const limit = pLimit(10);               // at most 10 in flight
const results = await Promise.all(
  userIds.map(id => limit(() => fetchUser(id)))
);

When NOT to use this pattern:

• When operations depend on each other (need the result of step i to issue step i+1) — that data dependency forces sequencing.
• When the downstream system is rate-limited or fragile — use bounded concurrency (p-limit, asyncio.Semaphore) rather than unbounded Promise.all.

Reference: MDN — `Promise.all`

Group by Key Instead of Cartesian Comparison

"For each pair (i, j), check if they share property X" is O(n²) by construction — but the question is almost always equivalent to "group items by property X, then look at groups with more than one member," which is O(n). The pairwise version inspects n(n-1)/2 pairs; the grouped version walks the list once. The trick is recognizing that the inner condition (a.email == b.email) defines an equivalence class on a hashable key — and equivalence classes are exactly what defaultdict(list) builds for free.

Incorrect (compare every pair — O(n²)):

duplicates = []
for i in range(len(records)):
    for j in range(i + 1, len(records)):
        if records[i].email == records[j].email:
            duplicates.append((records[i], records[j]))
# 10,000 records → ~50,000,000 comparisons

Correct (group by key — O(n)):

from collections import defaultdict
buckets = defaultdict(list)
for r in records:
    buckets[r.email].append(r)              # O(1)
duplicates = [bucket for bucket in buckets.values() if len(bucket) > 1]
# 10,000 records → 10,000 inserts + one walk over buckets

When NOT to use this pattern:

• When the equivalence relation is non-transitive (e.g., "names within edit-distance 2 of each other") — grouping by key doesn't apply; reach for clustering, blocking, or locality-sensitive hashing.
• When you need every pair (not just the existence of one) for downstream pairwise scoring — then the n² work is intrinsic.

Reference: NIST DADS — equivalence relation

Replace Pairwise Loops With Hash-Based Single Passes

Two nested loops over the same collection — even when the inner loop starts at i+1 — produce O(n²) work. At n=10,000 that's 100 million comparisons; at n=1,000,000 it's a trillion. The pattern is almost always avoidable by passing through the data once and remembering what was seen in a hash set or map. The key insight: "have I seen X before?" is an O(1) question when you maintain the right index, not an O(n) re-scan.

Incorrect (pairwise comparison — O(n²)):

duplicates = set()
for i, a in enumerate(items):
    for j, b in enumerate(items):
        if i != j and a == b:
            duplicates.add(a)
# 10,000 items → 100,000,000 iterations, ~seconds of CPU

Correct (single pass with a set — O(n)):

seen = set()
duplicates = set()
for item in items:
    if item in seen:        # O(1) lookup
        duplicates.add(item)
    seen.add(item)
# 10,000 items → 10,000 iterations, ~milliseconds

When NOT to use this pattern:

• When n is provably tiny (< ~30) and bounded — the hash overhead may dominate, and a nested loop is clearer.
• When the comparison requires fuzzy matching (similarity, distance) where no hash key applies — consider blocking, LSH, or a spatial index instead.

Reference: Python Time Complexity — set lookup is O(1) amortized

Index Lookups Once Instead of .find() per Iteration

Joining two collections in application code — "for each order, find its user" — naturally invites .find() in a .map(). Each .find() is O(users), making the whole join O(orders × users). Building a Map keyed by the join field once is O(users); subsequent lookups are O(1). The complexity flips from quadratic to linear, and the diff is two lines.

Incorrect (application-side join via `.find()` — O(orders × users)):

const enriched = orders.map(o => ({
  ...o,
  user: users.find(u => u.id === o.userId),  // scans users each call
}));
// 5,000 orders × 20,000 users = 100,000,000 comparisons

Correct (build index once — O(orders + users)):

const userById = new Map(users.map(u => [u.id, u]));   // O(users)
const enriched = orders.map(o => ({
  ...o,
  user: userById.get(o.userId),                        // O(1)
}));
// 5,000 + 20,000 = 25,000 operations

Alternative (database-side join):

If both collections originate from the same data source, push the join down to SQL or to your ORM's eager-loading mechanism — see `io-missing-eager-load`. Application-side joins are appropriate when the two sources are different (e.g., DB rows + external API responses).

Reference: MDN — `Map.prototype.get` runs in sublinear average time

Avoid .includes() / .indexOf() Inside a Loop

Array.prototype.includes, indexOf, find, and Python's x in list all scan linearly — O(n) per call. Calling any of them inside a loop over another collection produces O(n*m) complexity that reads like O(n). This is the single most common hidden-quadratic pattern in production code because the call site looks innocuous: one method call per iteration, no visible nesting. The fix is to pre-build a Set (or Map) once and convert each membership test from O(n) to O(1).

*Incorrect (looks linear, runs quadratic — O(nm)):**

// Filter sign-ups that aren't already users
const newSignups = recentSignups.filter(s =>
  !existingUsers.includes(s.email)  // O(existingUsers) per signup
);
// 1,000 signups × 50,000 existing users = 50,000,000 comparisons

Correct (set membership — O(n+m)):

const known = new Set(existingUsers);                  // O(m) once
const newSignups = recentSignups.filter(s =>
  !known.has(s.email)                                  // O(1) per signup
);
// 1,000 + 50,000 = 51,000 operations total

When NOT to use this pattern:

• When existingUsers is genuinely small (≲ 50) and the inner code is hot enough that hashing the key costs more than scanning — measure first.
• When elements are not hashable (mutable objects without stable identity); use a WeakSet for object identity or extract a stable key.

Reference: MDN — `Set.prototype.has` runs in average O(1)

Use Sets for Intersection, Union, and Difference

Computing A ∩ B, A ∪ B, or A \ B with list-based membership tests (x in list, Array.includes) is O(|A| × |B|). Converting the inner collection to a hash set once is O(|B|); subsequent membership tests are O(1), and the whole operation drops to O(|A| + |B|). Python, JavaScript, Java, and Go all expose hash sets in the standard library with this exact use case in mind — there is essentially no reason to compute set operations against an unhashed list.

*Incorrect (list-based membership — O(nm)):**

# Intersection: items in both A and B
common = [x for x in list_a if x in list_b]   # `x in list_b` scans list_b
# Difference: items in A not in B
only_in_a = [x for x in list_a if x not in list_b]

Correct (hash set — O(n+m)):

b_set = set(list_b)                           # O(m) once
common = [x for x in list_a if x in b_set]    # O(1) per check
only_in_a = [x for x in list_a if x not in b_set]

Alternative (when order doesn't matter):

common = set(list_a) & set(list_b)            # O(n + m)
only_in_a = set(list_a) - set(list_b)

When NOT to use this pattern:

• When elements are unhashable (e.g., dicts, lists). Either extract a hashable key (tuple(sorted(d.items()))) or accept the quadratic cost when n is small.
• When you need duplicates preserved — sets collapse them; use collections.Counter for multiset semantics.

Reference: Python Time Complexity — set operations

Tokenize Once Instead of Re-scanning a String per Pattern

pattern in text (Python) or text.includes(pattern) (JS) scans the full text — O(L) where L is text length. Looping over p patterns and running this check produces O(p*L) per document, which is fine for tiny p but catastrophic when you scan thousands of keywords against thousands of documents. When patterns are whole tokens, the rewrite is trivial: tokenize the text once into a set, then each membership test is O(1). When patterns are arbitrary substrings, use a multi-pattern algorithm (Aho-Corasick) that scans the text once and matches all patterns in a single pass — O(L + p + matches).

Note: the tokenize approach changes matching semantics from substring to whole-token — "cat" in "concatenate" is true for in, false after tokenization. For substring matching across multiple patterns, use Aho-Corasick.

*Incorrect (re-scan per pattern — O(pL)):**

flagged = []
for keyword in BANNED_KEYWORDS:          # p ~ 5,000
    for doc in documents:                 # d ~ 10,000
        if keyword in doc.body:           # O(L)
            flagged.append((doc, keyword))
# 5,000 × 10,000 × avg_doc_length scans

Correct (tokenize once when patterns are whole tokens — O(L + p)):

banned = set(BANNED_KEYWORDS)             # O(p)
flagged = []
for doc in documents:
    tokens = set(doc.body.split())        # O(L) once per doc
    for hit in tokens & banned:           # O(min(L, p))
        flagged.append((doc, hit))

Alternative (Aho-Corasick for arbitrary substrings):

import ahocorasick
A = ahocorasick.Automaton()
for kw in BANNED_KEYWORDS:
    A.add_word(kw, kw)
A.make_automaton()

for doc in documents:
    for end_idx, kw in A.iter(doc.body):  # one scan finds all patterns
        flagged.append((doc, kw))

When NOT to use this pattern:

• When p is small (≲ 10) and L is large — the per-pattern scan is already cheap and a tokenize-then-set conversion may not pay for itself.
• When patterns include regex (anchors, alternation, lookaround) — switch to a single combined regex with alternation, or a regex-trie library.

Reference: Aho–Corasick algorithm — NIST DADS

Use an Explicit Stack Instead of Deep Recursion

Recursion is bounded by the language's call-stack depth — typically ~1,000 frames in CPython (default sys.setrecursionlimit(1000)), ~10,000 in V8. Algorithms with recursion depth proportional to input size (linked-list traversal, deeply nested JSON walking, naive tree walks on degenerate trees) crash at scale even when their Big-O is fine. Converting to an explicit stack/queue eliminates the depth limit and removes per-call frame overhead. Crucially, neither CPython nor mainstream JS engines perform tail-call optimization — writing tail-recursive code does not save the stack.

Incorrect (recursion depth = list length — crashes at ~1,000 nodes):

def sum_list(node):
    if node is None:
        return 0
    return node.value + sum_list(node.next)
# 5,000-node list → RecursionError: maximum recursion depth exceeded

Correct (iterative with explicit loop — unlimited depth):

def sum_list(node):
    total = 0
    while node is not None:
        total += node.value
        node = node.next
    return total

Alternative (tree traversal with explicit stack):

def walk(root):
    stack = [root]
    while stack:
        node = stack.pop()
        process(node)
        stack.extend(node.children)        # pushes are O(1)
# Depth is now limited by heap, not call stack

When NOT to use this pattern:

• When recursion depth is provably O(log n) (balanced tree traversal) — stack depth is tiny and recursion is much clearer.
• In Scheme, Scala, or other languages with guaranteed tail-call optimization — tail-recursive form is idiomatic and safe.

Reference: CPython `sys.setrecursionlimit` — default 1000, not optimized for deep recursion

Memoize Recursion With Overlapping Subproblems

A recursive function that calls itself with arguments it has already computed for is doing the same work many times — and the count of repeat computations grows exponentially with depth. Fibonacci is the canonical example: fib(30) makes over 2.6 million calls to compute 31 distinct values. The structural fix is memoization — cache the result keyed by the arguments, return it on the next call. The recursion shape doesn't change; the cache turns an exponential tree into a linear DAG.

The signal: a recursion whose subcalls overlap (same arguments reached via different paths) is always worth memoizing.

Incorrect (exponential — O(2ⁿ)):

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
# fib(30) → 2,692,537 function calls
# fib(40) → 331,160,281 calls (~3 seconds in CPython)

Correct (memoized — O(n)):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
# fib(30) → 31 calls, fib(40) → 41 calls (microseconds)

Alternative (manual memo when key is non-hashable):

def edit_distance(a, b, memo=None):
    memo = memo if memo is not None else {}
    if (len(a), len(b)) in memo:
        return memo[(len(a), len(b))]
    # ... compute ...
    memo[(len(a), len(b))] = result
    return result

When NOT to use this pattern:

• When subproblems are unique (no overlap) — memoization adds bookkeeping for no benefit. Example: tree traversal where every subtree is visited exactly once.
• When cache size would exceed memory — bound maxsize or switch to tabulation; see `rec-tabulate-bottom-up`.

Reference: Python `functools.lru_cache` — memoization decorator

Prune Recursive Search With Bounds and Constraints

Combinatorial search problems — subset sum, knapsack, traveling salesman, constraint solving, AI search — are exponential in worst case, but most real instances admit massive pruning. A best-so-far bound that compares against the current partial solution lets you abandon branches that cannot possibly improve it; constraint propagation eliminates entire subtrees before exploring them. The general pattern: track an upper/lower bound, cheaply estimate the best possible completion at each node, prune branches that can't beat the current best. The Big-O stays exponential but constant factors collapse — what was 2⁴⁰ becomes a few million nodes.

Incorrect (brute-force enumeration — O(2ⁿ) every time):

def subset_sum(nums, target):
    """Does any subset sum to target?"""
    def helper(i, current):
        if current == target:
            return True
        if i == len(nums):
            return False
        # Try both: include nums[i], or skip it
        return helper(i + 1, current + nums[i]) or helper(i + 1, current)

    return helper(0, 0)
# n=30 → 2^30 ≈ 1 billion calls in worst case

Correct (prune when partial sum overshoots or sort by largest first):

def subset_sum(nums, target):
    nums = sorted(nums, reverse=True)        # largest first → fast overflow
    # Precompute suffix sums once — sum(nums[i:]) is O(1) via lookup, not O(n)
    suffix = [0] * (len(nums) + 1)
    for i in range(len(nums) - 1, -1, -1):
        suffix[i] = suffix[i + 1] + nums[i]

    def helper(i, current):
        if current == target:
            return True
        if current > target:                  # PRUNE: overshot
            return False
        if i == len(nums):
            return False
        # Optimistic bound: even taking all remaining, can we reach target?
        if current + suffix[i] < target:      # PRUNE: undershoot impossible
            return False
        return helper(i + 1, current + nums[i]) or helper(i + 1, current)

    return helper(0, 0)
# Same worst case but typically thousands of nodes, not billions —
# and each node is O(1), not O(n) as a naive sum(nums[i:]) would make it

Alternative (constraint propagation — Sudoku / SAT solvers):

# When picking a value forces or excludes values elsewhere, propagate immediately
# instead of recursing into branches that constraint violation will reject

When NOT to use this pattern:

• When the search space is small enough that brute force is faster than designing bounds — pruning has overhead.
• When the problem has provable polynomial structure (it's not actually combinatorial) — use DP or a polynomial algorithm instead.

Reference: Branch and bound (NIST DADS)

Share Memoization Across Top-Level Calls

Memoization confined to a single call is wasted when the same function is invoked many times with overlapping inputs — each call starts with an empty cache, re-computing what an earlier call already solved. The fix is to lift the memo out of the call (instance attribute, module-level dict, lru_cache on the function itself) so subsequent invocations reuse prior results. This is especially important when serving batched requests: 1,000 queries that each compute fib(40) should share one memo, not allocate 1,000 of them.

Incorrect (cache reset on every call — repeats all work):

def compute(n):
    memo = {}                              # fresh memo every invocation
    def helper(x):
        if x in memo:
            return memo[x]
        # ... recursive work ...
        memo[x] = result
        return result
    return helper(n)

# Batch query
for n in queries:                          # 1,000 queries
    results.append(compute(n))             # each pays full O(n) recursion

Correct (module-level `lru_cache` — shared across all callers):

@lru_cache(maxsize=10_000)
def compute(n):
    if n < 2:
        return n
    return compute(n - 1) + compute(n - 2)

for n in queries:
    results.append(compute(n))             # second call onward: O(1) cache hits

Alternative (instance-scoped cache for stateful classes):

class Solver:
    def __init__(self):
        self._memo = {}

    def compute(self, n):
        if n in self._memo:
            return self._memo[n]
        result = ...   # recursive work, using self.compute for subproblems
        self._memo[n] = result
        return result
# One Solver instance, many queries → shared cache

When NOT to use this pattern:

• When the function's result depends on hidden state (current time, RNG, mutable globals) — cached results become stale.
• When the cache would grow unbounded over a long-running process — set maxsize on lru_cache or use a TTL cache.

Reference: Python `functools.lru_cache` — function-level cache survives across all callers

Tabulate Bottom-Up to Eliminate Recursion Overhead

Memoized recursion (top-down DP) and tabulation (bottom-up DP) have the same Big-O, but tabulation is faster in practice on most runtimes (no function-call overhead, no hash lookups on the memo, better cache locality on a contiguous array) and trivially space-bounded. The conversion is mechanical: identify the dependency order of subproblems, allocate a table sized to the input, fill it in that order. Tabulation also makes the rolling-array space optimization obvious — if f(n) only depends on f(n-1) and f(n-2), you only need two variables, not a length-n array.

Incorrect (top-down memoization — same Big-O, but pays call/cache overhead):

@lru_cache(None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
# O(n) time, O(n) space — and pays Python's function-call overhead n times

Correct (bottom-up tabulation — faster constants, O(1) space):

def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b
# O(n) time, O(1) space — pure arithmetic in a tight loop

Alternative (2-D problem with rolling rows — O(n) space instead of O(n²)):

def edit_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        curr = [i] + [0] * len(b)
        for j, y in enumerate(b, 1):
            curr[j] = prev[j - 1] if x == y else 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr
    return prev[-1]
# O(|a|*|b|) time but only O(|b|) space — useful when one string is large

When NOT to use this pattern:

• When the subproblem space is sparse (most cells in the table never accessed) — top-down memoization only fills the cells it needs.
• When the dependency order is hard to derive — start with top-down memoization, then convert once correctness is established.

Reference: Sedgewick & Wayne, Algorithms 4e — Dynamic Programming

Use Binary Search on Sorted Data

If the underlying data is already sorted (or you'll sort it once and query many times), linear scanning to find a value, a boundary, or a range is leaving log-factor speedup on the table. Binary search is O(log n): 1,000,000 elements → 20 comparisons versus 1,000,000. The standard library exposes it directly — bisect_left/bisect_right (Python), Arrays.binarySearch (Java), std::lower_bound (C++), sort.Search (Go). For JavaScript, write a 10-line bisect helper; the cost is trivial compared to the speedup.

Incorrect (linear scan against sorted data — O(n) per call):

sorted_timestamps = [...]            # sorted, 1,000,000 entries

def first_after(t):
    for i, ts in enumerate(sorted_timestamps):
        if ts >= t:
            return i
    return None
# 10,000 queries × 500k avg scan = 5,000,000,000 comparisons

Correct (binary search — O(log n) per call):

import bisect
def first_after(t):
    return bisect.bisect_left(sorted_timestamps, t)
# 10,000 queries × ~20 comparisons = 200,000 comparisons total

Alternative (range queries with both bounds):

def items_in_range(lo, hi):
    left = bisect.bisect_left(sorted_timestamps, lo)
    right = bisect.bisect_right(sorted_timestamps, hi)
    return sorted_timestamps[left:right]      # O(log n + k)

When NOT to use this pattern:

• When data is not sorted and you can only insert (not rebuild) — binary search doesn't apply to unsorted data. Use a hash structure or a balanced tree.
• When the array is tiny (< 50 items) — the constant factor of bisect can match linear scan; favor readability.

Reference: Python `bisect` — Array bisection algorithm

Build the Index Once When Queries Dominate

A hash index, a sorted array, or a trie costs O(n) (or O(n log n)) to build but turns each subsequent lookup from O(n) to O(1) or O(log n). When the data is static during a batch of queries — common in batch jobs, request-scoped caches, and analytics pipelines — build the index once outside the query loop. The amortized cost over q queries is O(n + q) instead of O(q*n). Even a single extra lookup against the same data is often enough to justify the build.

The decision question: how many lookups will this index serve? If it's "one," skip it. If it's "two or more," build it.

Incorrect (linear scan per query, no shared work):

def annotate(orders, users):
    enriched = []
    for o in orders:                                # q = len(orders)
        user = next((u for u in users if u.id == o.user_id), None)
        enriched.append((o, user))
    return enriched
# 10,000 orders × 50,000 users = 500,000,000 comparisons

Correct (build once, query many — O(n + q)):

def annotate(orders, users):
    by_id = {u.id: u for u in users}                # O(|users|) once
    return [(o, by_id.get(o.user_id)) for o in orders]   # O(1) each
# 50,000 + 10,000 = 60,000 ops

Alternative (request-scoped cache — reuse index across requests):

# Build an index at startup, refresh on data change
USER_INDEX = {}

def reload_users():
    global USER_INDEX
    USER_INDEX = {u.id: u for u in fetch_all_users()}

def get_user(user_id):
    return USER_INDEX.get(user_id)
# Cost of build is amortized over every request the index serves

When NOT to use this pattern:

• When the index would consume more memory than the working set tolerates — sort-and-bisect uses no extra memory.
• When data changes between every query — the index is stale before it's used. Use a database with maintained indexes instead.

Reference: Use The Index, Luke — indexing for query speed

Use Quickselect for the K-th Element, Not Full Sort

Finding the median, the 90th percentile, or the k-th smallest doesn't require a full sort. Quickselect (a.k.a. std::nth_element) finds the k-th element in O(n) average time by partitioning around a pivot and recursing only into the half that contains the target. The full result list isn't materialized, but the element at position k is correct and everything to its left is ≤ everything to its right. This is the right tool for percentile calculations, "median of medians" queries, and "find the closest k points" subproblems.

Incorrect (full sort for one element — O(n log n)):

def percentile(values, p):
    sorted_vals = sorted(values)             # O(n log n)
    return sorted_vals[int(len(values) * p)]
# 10,000,000 values for one p95 query: O(n log n) ≈ 230M ops

Correct (quickselect — O(n) average):

import heapq

def percentile(values, p):
    k = int(len(values) * p)
    return heapq.nsmallest(k + 1, values)[-1]
# heapq.nsmallest uses partial sort: O(n log k) — when k is small, ~linear

Alternative (C++ `std::nth_element` — true O(n) average):

std::vector<int> values = ...;
auto kth = values.begin() + values.size() / 2;
std::nth_element(values.begin(), kth, values.end());   // O(n) avg
int median = *kth;

Alternative (Numpy `partition` — vectorized quickselect):

import numpy as np
arr = np.asarray(values)
k = int(len(arr) * 0.95)
np.partition(arr, k)[k]    # O(n) average, vectorized

When NOT to use this pattern:

• When you also need the elements before k in sorted order — quickselect doesn't sort them; if you need both, sort once.
• When you need many percentiles at once (p50, p90, p99) on the same data — sort once and index O(1).

Reference: Quickselect algorithm — Wikipedia

Sort Once Outside the Loop, Not on Every Iteration

Sorting is O(n log n) per call — already not free. Re-running the same sort on the same array inside a loop multiplies that by the loop length: O(n² log n) total for n iterations against an n-element array. This pattern appears in "find the median of this list" or "the k smallest" called per request, where the underlying list rarely changes. Sort once at module load (or whenever the data is updated), cache the sorted view, query it as needed.

Incorrect (sort per iteration — O(n² log n)):

scores = [...]                          # 10,000 scores, mostly static

def report_top_5_for_request(request):
    sorted_scores = sorted(scores, reverse=True)   # O(n log n) each request
    return sorted_scores[:5]
# 100 requests/sec × 10,000 × log(10,000) ≈ 13M ops/sec just sorting

Correct (sort once, maintain on update):

sorted_scores = sorted(scores, reverse=True)       # once

def report_top_5_for_request(request):
    return sorted_scores[:5]                       # O(1)

def add_score(new_score):
    bisect.insort(sorted_scores, new_score)        # O(log n) lookup + O(n) shift

Alternative (when insertions dominate — heap):

import heapq
# For "always read top-k, frequent inserts" use a heap, not a sorted list
top_k = []
def add(score):
    if len(top_k) < 5:
        heapq.heappush(top_k, score)
    else:
        heapq.heappushpop(top_k, score)

When NOT to use this pattern:

• When the underlying list changes more often than it's queried — sorting on read is fine; lazy approaches are wasteful.
• When the comparator depends on per-request state (sort by relevance to this user) — you can't precompute; consider partial sort or top-k heap instead.

Reference: Python `sorted` is Timsort, O(n log n) worst case

Pipe Through Generators Instead of Materializing Intermediate Lists

Chaining map(...), filter(...), then sum(...) over a list with eager evaluation builds a new full list at each stage — three passes over n items, each allocating n elements. A generator pipeline (Python generator expressions, JS iterator helpers, Java Stream, Go channels) walks the data once, lazily, producing each result on demand. Memory drops from O(n) of intermediate allocations to O(1), and short-circuit consumers (next, any, all, find) can stop as soon as the answer is known.

Incorrect (materialized intermediates — O(n) extra memory per stage):

squared = [x * x for x in numbers]            # allocates list of size n
positives = [x for x in squared if x > 0]     # allocates again
total = sum(positives)                         # walks again
# 3 × n allocations + 3 passes

Correct (generator pipeline — O(1) memory, one pass):

total = sum(x * x for x in numbers if x * x > 0)
# Single fused pass, no intermediate list allocation

Alternative (generator function with early termination):

def positive_squares(nums):
    for x in nums:
        sq = x * x
        if sq > 0:
            yield sq

# Caller can stop as soon as a condition is met
first_big = next(sq for sq in positive_squares(numbers) if sq > 1_000_000)

Alternative (JS — generator function):

function* positiveSquares(nums) {
  for (const x of nums) {
    const sq = x * x;
    if (sq > 0) yield sq;
  }
}
// Memory: O(1). And: stops early if consumer breaks

When NOT to use this pattern:

• When you need to iterate the same data multiple times — generators are single-pass; materialize the result if you'll reuse it.
• When you need indexed/random access — generators only support sequential iteration.

Reference: PEP 289 — Generator Expressions

Release References That Prevent Garbage Collection

A garbage collector reclaims only what's unreachable. Long-lived containers (module-level caches, event listeners, timers, closures captured by long-lived callbacks) keep transitively-reachable objects alive forever — what looks like a memory leak in a GC'd language is almost always an unintended retained reference. In long-running services, this manifests as a slow heap creep that eventually triggers GC pauses (latency spikes), then OOM hours or days later. The fixes are mechanical once you recognize the pattern: bounded caches, weak references for parent→child back-pointers, explicit unsubscription, and avoiding closing over heavy state in callbacks.

Incorrect (unbounded cache + closure over heavy state):

const cache = new Map();   // module-level, never trimmed

function handleRequest(req) {
  const heavyResponse = expensiveCompute(req);
  cache.set(req.id, () => heavyResponse);   // closure pins `heavyResponse` forever
  // …
}
// Every request leaves a closure that retains the full response object

Correct (bounded cache, no closure over heavy state):

import LRU from 'lru-cache';
const cache = new LRU({ max: 1000 });     // bounded, evicts oldest

function handleRequest(req) {
  const heavyResponse = expensiveCompute(req);
  cache.set(req.id, summarize(heavyResponse));   // store only what's needed
}

Alternative (weak references for parent→child pointers):

// Avoid: child pinning parent in memory because parent.children[] points to child
class Parent {
  constructor() { this.children = []; }
}
class Child {
  constructor(parent) { this.parent = parent; }   // back-pointer pins parent
}

// Better: WeakRef for the back-pointer
class Child {
  constructor(parent) { this.parentRef = new WeakRef(parent); }
  getParent() { return this.parentRef.deref(); }
}

Alternative (clean up event listeners and timers):

// Long-lived listener pins everything its closure references
useEffect(() => {
  const handler = e => doSomething(state);
  window.addEventListener('resize', handler);
  return () => window.removeEventListener('resize', handler);   // critical
}, [state]);

When NOT to use this pattern:

• For short-lived processes (CLI scripts, request handlers) — retention doesn't matter; GC will reclaim everything when the process exits.

Reference: V8 blog — understanding garbage collection and retention

Use Shallow Copies (or No Copy) Instead of Deep Clones

copy.deepcopy(x), JSON.parse(JSON.stringify(x)), and structuredClone(x) recursively walk the entire object graph allocating every node. That's necessary when you must isolate mutation; it's wasteful when the caller is read-only or only modifies the top level. Default to no copy at all (just pass the reference), shallow copy when you need to mutate the container ({...obj}, [...arr], dict(d)), and reach for deep copy only when you've identified a specific aliasing bug that needs it. Deep cloning a large nested object on a hot path is a common source of mysterious latency.

Incorrect (deep clone the world — O(total nodes)):

function recordSnapshot(state) {
  history.push(structuredClone(state));   // deep walks every nested object
}
// state with 10,000 nodes × 100 snapshots = 1,000,000 allocations

Correct (shallow copy at the level you'll mutate):

function updateField(state, key, value) {
  return { ...state, [key]: value };      // copies top-level keys only
}
// state with 10,000 nested nodes → ~50 top-level pointer copies

Alternative (Python — be explicit about copy depth):

import copy

# Wrong default: deepcopy everywhere "just in case"
fresh = copy.deepcopy(original)        # walks the whole tree

# Right: only what's needed
fresh = original.copy()                # dict/list shallow copy — O(top-level)
fresh = {**original, 'k': new_value}   # update one key, share the rest

When NOT to use this pattern:

• When you genuinely need an isolated copy you'll mutate deeply — e.g., test fixtures, undo/redo with full divergence. Deep copy is correct.
• When the structure has cycles — structuredClone and copy.deepcopy handle them; manual shallow copy doesn't.

Reference: MDN — `structuredClone` is a deep clone (use sparingly)

Stream Large Inputs Instead of Loading Them Whole

Reading a 5GB file with open(path).read() allocates 5GB in memory before you can process the first byte. Most line-oriented or chunk-oriented processing doesn't need the whole file resident — the natural shape is "for each line, do X." Iterating over the file handle yields one line at a time, with O(1) memory regardless of file size. The same applies to network streams (use iter_content/iter_lines), database cursors (.fetchmany / server-side cursors), and large API paginated responses. Beyond memory, streaming gives you "first byte" latency — the consumer can start producing output before the whole input is read.

Incorrect (load entire file — O(file size) memory):

with open('access.log') as f:
    lines = f.readlines()                  # allocates the whole file
for line in lines:
    process(line)
# 5GB file → 5GB RAM, OOM on small instances

Correct (stream — O(1) memory):

with open('access.log') as f:
    for line in f:                         # yields one line at a time
        process(line)
# Constant memory regardless of file size

Alternative (Node.js streams for HTTP body / file):

import { createReadStream } from 'node:fs';
import readline from 'node:readline';

const rl = readline.createInterface({ input: createReadStream(path) });
for await (const line of rl) {
  process(line);
}

Alternative (database — server-side cursor):

# psycopg2: named cursor enables server-side iteration without loading all rows
with conn.cursor(name='stream_rows') as cur:
    cur.itersize = 1000
    cur.execute("SELECT * FROM events")
    for row in cur:                        # batches of 1000, not all at once
        process(row)

When NOT to use this pattern:

• When the algorithm requires random access across the file (e.g., reverse iteration, sort) — you must materialize, but consider mmap for OS-managed paging.
• When the file is small (< 100MB on a modern machine) — load and process is simpler and the memory cost is negligible.

Reference: Python file objects support iteration line-by-line