Data structures, complexity, and the real bottleneck

Status: Complete. Last reviewed 2026-08-28.

Data-structure and algorithm vocabulary is useful when it predicts how a system changes under load. It is not a substitute for a production cost model. A senior backend answer connects input shape to operations, operations to resources, and resources to measured latency, memory, throughput, or contention.

Start with the contract, not the container

A data structure is a set of operations and guarantees, not merely a type name. Before selecting one, state what the caller needs:

preserve order, sort order, or neither;
keep duplicates or enforce uniqueness;
find by a stable key, scan by a predicate, or access by position;
insert and remove frequently or build once and read many times;
maintain a bounded working set or retain the entire history;
share durably across requests or use only inside one process.

A sequence is the right abstraction when order and iteration dominate. A set expresses membership and uniqueness. A map associates unique keys with values. A queue exposes first-in/first-out removal, while a stack exposes last-in/first-out removal. A priority queue removes by priority rather than arrival. A tree supports hierarchical or ordered traversal; a graph represents arbitrary relationships. Those contracts matter more than whether a particular implementation uses hashing, contiguous storage, linked nodes, or a tree.

The same logical structure can have different physical costs. PHP’s built-in array is an ordered map with integer or string keys, so it conveniently represents lists, maps, sets-by-key, and records. That flexibility does not make it a compact vector, a typed record, or a uniqueness-enforcing set. For large in-memory workloads, representation overhead and key semantics may justify a dedicated structure, an object, a database operation, streaming, or moving the computation to a more suitable boundary.

Complexity is a growth model

Big O describes an upper growth class as input size increases, normally ignoring constant factors and lower-order terms. It does not predict seconds, CPU instructions, network trips, memory locality, or the size at which one approach wins. Big Theta describes a tight asymptotic bound; Big Omega describes a lower bound. In everyday interview discussion, people often say “Big O” when they mean the dominant growth rate, so clarify the case and assumptions rather than debating notation alone.

Always name the variable. O(n) could mean number of rows returned, rows examined, tenants, bytes, graph vertices, or jobs. With two independent collections, a join-like nested scan is O(nm), not automatically O(n²). If the collections are bounded differently, collapsing them to one symbol hides the design constraint.

Operation	Expected or typical time	Important qualification
Scan a sequence	O(n)	It may stop early; work per item can dominate.
Lookup in a hash map	O(1) average	Hashing, collisions, resizing, and memory are real costs; worst-case guarantees differ by implementation.
Lookup in a balanced search tree	O(log n)	It also preserves sorted traversal, unlike a hash map.
Binary search in a sorted random-access sequence	O(log n)	Maintaining sorted order or copying into a searchable representation has a cost.
Comparison sort	O(n log n) typical	Comparator work, allocation, stability, and input distribution matter.
Heap insertion/removal	O(log n)	Reading the highest-priority item is commonly O(1).
Graph traversal	O(V + E)	Memory and repeated remote fetches can dominate traversal work.

Space complexity belongs in the same answer. Replacing repeated scans with a lookup map often changes time from O(nm) to expected O(n + m), but retains an additional O(m) index for the indexed collection. That is often an excellent server-side trade, until the index exceeds the process memory budget or the input could have been joined and filtered by the database.

Amortized analysis describes an average across a sequence of operations. Appending to a growable structure can be amortized O(1) even though an occasional resize is O(n). That is not the same as average-case analysis over random inputs, and neither is a latency guarantee for an individual request.

Trace the operation count before optimizing

Consider matching incoming line items to a product catalogue. Scanning all products for every item performs up to n × m comparisons:

foreach ($lineItems as $lineItem) {
    foreach ($products as $product) {
        if ($product->sku === $lineItem->sku) {
            // Use the product.
            break;
        }
    }
}

Building a map performs one catalogue pass and then expected constant-time lookups:

$productsBySku = [];

foreach ($products as $product) {
    $productsBySku[$product->sku] = $product;
}

foreach ($lineItems as $lineItem) {
    $product = $productsBySku[$lineItem->sku] ?? null;
}

The rewrite also changes semantics. Duplicate SKUs are silently overwritten unless detected, the whole catalogue remains live in memory, and key normalization must match the domain. The algorithm is correct only after defining whether duplicate catalogue rows are impossible, erroneous, or meaningful.

If products live in a database, fetching the catalogue and indexing it in PHP may be the wrong boundary. A set-based query with a suitable index can filter or join near the data. Conversely, issuing one query per line item turns an apparently O(n) loop into n network round trips and repeated planning/execution. The source code’s loop count is not the system’s cost model.

Choose structures from workload shape

Use a linear scan when collections are small, construction of an index would cost as much as the single scan, or the predicate cannot be keyed usefully. Build a map or set when repeated lookup dominates and memory is acceptable. Preserve a sorted structure when range queries, ordered iteration, predecessor/successor lookup, or deterministic priority matter. Use a heap when repeatedly selecting the next highest- or lowest-priority item without fully sorting every time.

For bounded recent history, a ring buffer or fixed-capacity queue makes the retention policy structural. For an unbounded stream, do not turn streaming into “load everything, then loop.” Page or iterate incrementally, but define ordering, cursor stability, retry position, and resource lifetime. Streaming reduces peak retained data; it does not reduce total work and can hold database cursors or transactions open.

Recursion closely matches trees and divide-and-conquer algorithms, but PHP application code should consider depth, stack usage, cycle handling, and diagnosability. An explicit stack or queue makes memory ownership and maximum-work controls visible. For graphs, maintain a visited set unless revisiting is intentional; otherwise cycles can cause non-termination and shared subgraphs can cause repeated work.

Database indexes are data structures too. A composite B-tree can make a query scale with a narrow range instead of a broad scan, but write amplification, storage, cache pressure, column order, selectivity, and the actual query plan decide its value. “Use a hash map” in process and “add an index” in storage are both hypotheses that must respect ownership, persistence, consistency, and workload.

Find the real bottleneck

Begin with a user-visible or operational symptom and a budget: endpoint p95 latency, job throughput, memory ceiling, database CPU, queue age, or downstream error rate. Then decompose the path into waiting and service time across queueing, application CPU, database queries and locks, cache, remote calls, serialization, and response transfer.

Use evidence appropriate to the suspected resource:

Trace a representative slow request or job and count queries and remote calls.
Compare latency distributions, not only averages; separate queue wait from execution.
Inspect database execution plans, rows examined versus returned, lock waits, and connection-pool saturation.
Profile CPU and allocation when application computation is a material span.
Measure peak memory and payload cardinality for indexing, batching, and eager loading.
Reproduce with production-like input sizes and dependency behavior, then compare before and after.

An O(n²) computation over a small bounded set can be cheaper and clearer than building an index. An O(n) loop that makes sequential slow network calls is still slow despite excellent asymptotic notation. An O(log n) database lookup can wait behind a saturated connection pool or lock. Optimization should target the largest relevant term or the resource approaching saturation, not the most embarrassing-looking loop.

Tail behavior deserves special attention. A fast median can coexist with a bad p99 caused by occasional resizing, cache misses, lock contention, garbage collection, large tenants, or downstream retries. Segment measurements by input size and dependency outcome before claiming algorithmic causation.

Failure modes and decision traps

Optimizing without a baseline: a rewrite adds complexity while the database or network still dominates.
Ignoring construction cost: building and discarding a map for one lookup is slower and larger than scanning a small list.
Hiding I/O in iteration: accessors, ORM lazy loading, serializers, or callbacks create N+1 work.
Confusing expected with guaranteed: average O(1) lookup is presented as a hard latency bound.
Using one variable for different inputs: O(n²) hides that the real cost is O(users × permissions) with different caps.
Trading time for unbounded memory: a lookup index or memoization cache grows with tenant data or process lifetime.
Changing correctness while tuning: deduplication, ordering, null handling, or duplicate-key behavior changes silently.
Benchmarking an unrealistic hot path: tiny fixtures, warm caches, local dependencies, or averages conceal production tails.

Keep the simplest implementation that meets the measured budget and preserves the contract. Record the assumption that would trigger reconsideration: input cardinality, lookup frequency, memory headroom, query-plan change, latency objective, or dependency limit.

Current and legacy context

Current: PHP’s array remains an ordered map supporting integer and string keys. Its list-like syntax should not be mistaken for a compact array guarantee.
Common: Laravel collections and ORM models add expressive operations, but chained transformations can allocate intermediate collections or conceal database access. Inspect generated queries, materialization, and memory rather than inferring cost from fluent syntax.
Legacy: Hand-written loops are not inherently inferior to collection pipelines, and replacing them mechanically is not modernization. Prefer the representation whose behavior, type expectations, and cost can be explained.