Complexity And Growth

Complexity describes how time or memory grows as input grows, independent of one machine's exact timing.

Why This Matters

A loop that is harmless for 100 rows may dominate a request at 100,000 rows. Big-O is a comparison tool, not a substitute for measurement.

Working Model

Constant, logarithmic, linear, linearithmic, quadratic, and exponential growth describe broad scaling behavior. Include database, network, allocation, and serialization costs when reasoning about application code.

Practical Rules

• State the input size.
• Count nested or repeated work.
• Distinguish worst, average, and amortized behavior.
• Measure realistic data.
• Optimize only after identifying a meaningful cost.

Failure Modes

• Ignoring constants and I/O.
• Calling every nested loop quadratic without checking bounds.
• Using Big-O to claim one implementation is faster at all sizes.
• Optimizing tiny code while database calls dominate.

Verification

• Benchmark several input sizes.
• Plot or compare growth ratios.
• Profile the complete request.
• Retest after optimization.

What You Should Be Able To Do

After this lesson, you should be able to explain time and space complexity and how to connect growth analysis to measured PHP behavior, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Reading Growth In Real Programs

Complexity analysis is useful because it gives you a way to talk about growth before the program is too slow to reason about. A timing from your laptop can tell you that one run took 30 milliseconds, but it does not explain what will happen when the input is ten times larger, when the request includes more related records, or when the same code runs inside a worker with less memory. Big-O notation strips away exact machine timing and asks a narrower question: how does the amount of work grow as the input grows?

That abstraction is powerful, but it is easy to misuse. The input size must be named. In a PHP request, the input might be the number of uploaded rows, the number of products returned by a query, the number of users in a permission list, the number of characters in a string, or the number of edges in a dependency graph. If the team says only that a function is O(n), the next useful question is n of what? The answer determines whether the cost is harmless or dangerous. A loop over five configured payment methods is different from a loop over every order in the database.

Complexity also describes a model, not the whole runtime. A single database query can dominate a thousand in-memory operations. Allocating a large intermediate array can matter more than a comparator. Network latency, serialization, autoloading, filesystem access, and cache misses can hide the cost that looks largest on paper. The right habit is not to choose between theory and measurement. Use complexity to predict where growth can hurt, then measure the actual system at realistic sizes.

Common Growth Classes

Constant time, written O(1), means the modeled work does not grow with the named input. Looking up a key in a PHP array is usually treated as constant-time for application reasoning, even though the engine still does real work internally. Constant time does not mean free. It means that doubling the number of records being modeled should not double this operation's cost.

Logarithmic time, O(log n), grows slowly because each step discards a large portion of the remaining search space. Binary search is the standard example: each comparison removes roughly half the remaining sorted range. Logarithmic work is attractive, but it depends on an invariant. If the data is not sorted according to the same comparison rule used by the search, the cost may still be low while the answer is wrong.

Linear time, O(n), grows directly with the input. Scanning an array to find a matching identifier is linear because the worst case checks every element. Linear work is often fine. A clear linear pass over a hundred rows may be better than a complicated index that nobody maintains. Linear work becomes a problem when it sits inside a repeated request path or when the input is allowed to grow without a product limit.

Linearithmic time, O(n log n), often appears in efficient comparison sorting. Sorting can be a good investment when the sorted order is reused for many operations. It can be wasteful when a request sorts a large collection only to find one element once. The decision depends on the surrounding workflow, not on the growth class alone.

Quadratic time, O(n^2), usually comes from comparing each item with many other items. Nested loops are a warning sign, but they are not proof. A loop over 12 months inside a loop over users is not quadratic in users because the inner bound is fixed. A loop over all orders inside a loop over all users may be quadratic if both sets grow together. Always identify the variable bounds before naming the class.

Exponential behavior is the danger zone for ordinary application requests. Recursive exploration, backtracking, and combinatorial generation can explode even for modest inputs. If a feature truly needs that kind of search, it normally needs strict input limits, pruning, memoization, background processing, or a different model entirely.

A PHP Example: Repeated Scans

A common PHP performance bug is a repeated scan that looks harmless in small fixtures. Imagine an import task that receives order rows and product rows. The first implementation searches the product list for every order line:

<?php

declare(strict_types=1);

$products = [
    ['sku' => 'A100', 'name' => 'Notebook'],
    ['sku' => 'B200', 'name' => 'Pen'],
    ['sku' => 'C300', 'name' => 'Folder'],
];

$orderSkus = ['B200', 'C300'];

foreach ($orderSkus as $sku) {
    foreach ($products as $product) {
        if ($product['sku'] === $sku) {
            echo $product['name'] . PHP_EOL;
            break;
        }
    }
}

// Prints:
// Pen
// Folder

For two order lines and three products, the code is readable and fast. For 20,000 order lines and 20,000 products, the worst case is a very different shape. Each order line may scan much of the product list. The cost grows with the product of the two input sizes.

A better design builds a lookup map once, then performs key lookups:

<?php

declare(strict_types=1);

$products = [
    ['sku' => 'A100', 'name' => 'Notebook'],
    ['sku' => 'B200', 'name' => 'Pen'],
    ['sku' => 'C300', 'name' => 'Folder'],
];

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

foreach (['B200', 'C300'] as $sku) {
    echo $productsBySku[$sku]['name'] . PHP_EOL;
}

// Prints:
// Pen
// Folder

The improved shape is one linear pass to build the map, followed by one lookup per order line. That is usually a major improvement when the lookup is repeated. It is not automatically better for every case. The map uses extra memory, it must define what happens with duplicate SKUs, and it may be pointless if there is only one lookup. Complexity analysis helps you ask those questions explicitly.

Space Complexity Matters Too

Developers often discuss time first because slow requests are visible. Memory failures are just as real. A script can be linear in time and still unsuitable because it materializes a huge array. A controller that fetches every row, maps each row into a second array, groups the rows into a third array, and finally serializes JSON may hold several copies of related data at once.

Space complexity asks how memory grows with input. Streaming a CSV file line by line can keep memory close to constant with respect to the file length. Loading the whole file into an array grows with the number of rows. Grouping by user grows with the number of distinct users and the number of retained rows. When you state the complexity of a PHP task, include the memory model if the input can be large.

This is especially important for command-line workers and imports. A web request may fail quickly under a memory limit. A worker may process for minutes before it exhausts memory, leaving partial work and ambiguous progress. Measuring peak memory with realistic fixtures is often more useful than inspecting the algorithm alone.

Amortized And Hidden Costs

Some operations have occasional expensive steps that are acceptable when averaged across many operations. This is amortized reasoning. Dynamic storage, hash tables, buffers, and batched writes can behave this way. The important review question is whether the occasional expensive step can happen in a place where latency matters. A batch worker may tolerate it. A payment callback probably should not depend on a rare but large pause.

PHP also hides work behind convenient functions. array_map(), array_filter(), and array_values() can make code expressive, but they may allocate new arrays. Chaining several of them over large input can be more expensive than a single explicit loop that validates, transforms, and collects only the needed output. That does not mean functional helpers are bad. It means their allocation behavior belongs in the design when the data size is large.

Database work is another hidden cost. A loop that performs one query per item is often worse than an in-memory quadratic loop because it adds network and database planning overhead. The Big-O model should include the number of queries, not only the number of PHP comparisons. A profile that shows hundreds of similar queries is usually pointing at a data-loading problem, not at a need for clever syntax.

Choosing What To Optimize

Optimization starts with a concrete pain: a request is too slow, a worker misses its deadline, memory exceeds a limit, a database is overloaded, or a feature cannot handle the expected input size. Without that pressure, prefer simple code whose cost is easy to explain. Complexity analysis should prevent obviously bad growth from entering important paths, but it should not turn every small loop into a custom data structure.

When there is a real cost, isolate it. Measure the whole path first, then drill down. If the database accounts for most of the time, rewriting a PHP loop may not matter. If serialization dominates, changing a search structure may not help. If one nested loop accounts for the majority of CPU time, then replacing repeated scans with a map is a focused repair.

Use several input sizes when benchmarking. One run at one size can be misleading because caches, JIT warmup, database buffers, and operating system scheduling all affect timing. A growth check compares how the time changes as the size grows. If doubling the input roughly doubles the time, the measured behavior looks linear for that range. If doubling the input roughly quadruples the time, investigate quadratic work.

Verification And Review

A good review of complexity-related code states the expected input range, the chosen representation, the operation costs, and the measurement that supports the decision. For example: The import builds one SKU map because each order line performs a lookup; duplicate SKUs are rejected before the map is used; the benchmark covers 1k, 10k, and 100k rows; peak memory stays below the worker limit. That explanation is more useful than saying only that the code is faster.

Test boundary cases as well as size. Empty input should not fail accidentally. Duplicate identifiers should follow the documented policy. Malformed input should be rejected before expensive work begins. Sorted input, reverse-sorted input, and duplicate-heavy input can expose assumptions in algorithms that look fine on random fixtures.

After this lesson, you should be able to name the input size, describe the expected growth in time and memory, identify repeated work, decide when an index or map is justified, and prove the decision with measurements that match the real application path.