Algorithms and Resource Pressure

Suppose a service receives a list of account identifiers and must report the first duplicate. For a list of five entries, almost any reasonable program feels instant. For a list of ten million entries, the procedure—not the programming language’s reputation—decides whether the job finishes comfortably.

By the end of this lesson, you should be able to:

• compare two correct procedures by how their work grows with input size;
• trace a pair-by-pair duplicate check and a set-based check;
• use a simple cost model to reason about time, memory, and assumptions;
• explain why Big O describes a growth shape, not a stopwatch reading.

An algorithm is not judged only by whether it returns the right answer. It is also judged by how its work and memory use change as the input grows.

Core Insight

Resource pressure appears when an input that was once small becomes ordinary: a nightly import, a search index, a list of payments, or a stream of sensor readings. Two programs can be equally correct on every input and still have radically different futures.

To make that future visible, choose a unit of work. Here, count identifier comparisons or membership checks. Then call the number of input items n and ask how that count changes when n doubles. This is a model: deliberately simpler than a real machine, but useful because it exposes the dominant pattern.

The notation O(n²) says that work grows proportionally to the square of the input size, up to constant factors and smaller terms. O(n) says it grows roughly in step with the input. Those are claims about growth, not promises that one particular run takes a particular number of milliseconds.

The Small Situation

Consider this list, read from left to right:

AVA-12, MIKA-04, LEO-19, MIKA-04, SANA-77

We want the first identifier that has already appeared. One direct procedure is: for each identifier, compare it against every earlier identifier. When we reach the second MIKA-04, the comparison with the earlier MIKA-04 reveals the duplicate.

This procedure has attractive properties. It needs almost no extra storage, is easy to write, and does not rely on a special data structure. On a short list, it is a perfectly sensible choice. The question is what happens on a long list with no duplicate, because that forces the procedure to do all of its possible work.

A Better Model: Count the Work

For the first item there are zero earlier items to compare. For the second there is one; for the third there are two; and so on. With no duplicate, the total comparisons are:

0 + 1 + 2 + ... + (n - 1) = n(n - 1) / 2

The exact formula matters here because it makes the pattern concrete.

If n doubles, this quantity becomes close to four times as large. The n² in O(n²) is a compressed way of naming that shape. We ignore the division by two when comparing very large inputs because it does not change the crucial fact: every additional item can cause comparisons with many earlier items.

The Pair-by-Pair Procedure

Here is the procedure as pseudocode:

for each position i from left to right:
    for each earlier position j before i:
        if identifier[i] equals identifier[j]:
            return identifier[i]
return NONE

Trace it on the sample list. AVA-12 has no earlier item. MIKA-04 is compared with AVA-12. LEO-19 is compared with both earlier entries. At the fourth position, the program compares MIKA-04 with AVA-12, then with the earlier MIKA-04, and returns it.

Early success can make this look cheap. That is real: algorithms can have different best, average, and worst cases. But an operational decision also needs to consider the expensive cases. An import system cannot assume that every bad input conveniently reveals its duplicate near the front.

The pair-by-pair method uses O(1) additional memory beyond the input: it stores a few positions and the current values. Its price is repeated work. It keeps asking, “Have I seen this before?” by rebuilding the answer from comparisons already made.

A Second Procedure: Remember What We Saw

Instead, keep a set named seen. A set records whether a value is present. For each identifier, first ask whether it is already in the set; if it is, return it. Otherwise add it and continue.

seen = empty set
for each identifier from left to right:
    if identifier is in seen:
        return identifier
    add identifier to seen
return NONE

On the example, add AVA-12, MIKA-04, and LEO-19. When the second MIKA-04 arrives, its membership test succeeds immediately. The procedure returns without comparing it with every earlier value one by one.

With a typical hash-based set and well-behaved hashing, membership and insertion are expected to take approximately constant time on average. Repeating that work once per input item gives expected O(n) time. The gain comes from saved history: the set may contain up to n identifiers, so it uses O(n) additional memory.

“Expected” is an important word. A hash table is not magic and O(1) is not an unconditional law. Poor hash behavior, adversarial inputs, resizing, or a different set implementation can change the costs. A balanced-tree set, for example, often gives O(log n) membership rather than expected constant time, while preserving a different set of guarantees.

What the Model Lets Us Predict

The model now supports a useful prediction. If a no-duplicate list grows from 10,000 to 20,000 items, the pair-by-pair comparison count grows from about 50 million to about 200 million—nearly four times. The set-based procedure processes roughly twice as many items and retains roughly twice as many identifiers.

This prediction is often enough to narrow the design decision before benchmarking. It says where a problem will become painful. It does not remove the need to measure a production system: identifier length, allocation costs, cache behavior, database access, and language runtime can all dominate at a particular scale.

Think of Big O as a map with the terrain simplified. It helps distinguish a road that gets four times longer when the trip doubles from one that gets twice as long. It does not tell you about every traffic light.

Time, Memory, and Assumptions

Neither procedure is universally superior. A useful choice names the constraints.

• If the input is tiny or memory is extremely scarce, pair-by-pair comparison may be adequate and simpler.
• If the input is large and enough memory is available, remembering seen identifiers usually avoids prohibitive repeated work.
• If inputs arrive as an unbounded stream, an exact set grows without limit. You may need a retention window, external storage, or an approximate structure such as a Bloom filter—each with a changed guarantee.
• If the task requires a particular output order or must retain duplicate counts, the data structure and model must change with the requirement.

There is also a distinction between input memory and additional memory. The pair-by-pair version can reread the supplied list; the set version allocates a new summary of the values. Calling the latter “O(n) memory” is not a condemnation. It is a statement of what resource is being exchanged for less time.

Before changing an implementation, make the model testable. Record a representative input size, whether duplicates tend to appear early, the available memory budget, and the operation that actually dominates the service. Then benchmark both procedures with those conditions. If the measurements disagree with the model, investigate rather than discarding either one: perhaps reading the data dominates, perhaps the input is almost always tiny, or perhaps allocations and cache misses are the real pressure. Analysis tells you which questions to ask; measurement tells you how this particular system answers them.

Common Confusions

“O(n) is always faster than O(n²)." Not for every small input. Building a hash set has overhead, and a quadratic method can win at small sizes. The growth model tells you what tends to dominate as scale increases; measurements decide close cases.

“Big O gives the exact running time.” It deliberately hides constants, hardware, and implementation details. Use it to compare shapes of growth, then benchmark the real workload when a decision matters.

“The set makes duplicate detection free.” It moves the cost. Memory, hashing, allocation, and assumptions about average-case behavior are now part of the design.

“A correct answer proves the algorithm is good.” Correctness and resource use are separate dimensions. A correct algorithm may still miss a latency budget or exhaust available memory.

Check

A list of 1,000 distinct identifiers requires 499,500 pair comparisons in the model. What happens when the list grows to 2,000 distinct identifiers?

The answer is 1,999,000 comparisons: about four times as many, not twice. That is the signature of the quadratic pair-by-pair shape.

Now ask a second question: which assumption supports calling the set procedure expected O(n)? Each membership check and insertion must be approximately constant time on average. If that assumption is unsuitable, state a different data structure and its cost instead of repeating the slogan.

Practice

Take a familiar task: checking whether a username list contains duplicates, matching repeated product codes, or finding repeated words in a document.

1. Write the pair-by-pair procedure in plain language.
2. Identify the repeated work in its no-match case and express it as a sum.
3. Describe what information a set, map, or sorted structure would retain.
4. Name one time constraint, one memory constraint, and one assumption that could change your choice.

For an extra challenge, change the requirement from “find any duplicate” to “report every duplicated identifier and its count.” Notice that the set becomes a map from identifier to count. The algorithmic idea remains, but the stored representation changes because the question changed.

Resources

• [COURSE] MIT 6.006: Introduction to Algorithms — Use the early materials to connect growth analysis with concrete data structures.
• [BOOK] Open Data Structures — Read the set and hash-table chapters for implementations behind the model.
• [BOOK] Structure and Interpretation of Computer Programs — Return to it for procedures, abstraction, and how computational costs follow from a process.

Key Takeaways

• Two algorithms can return the same result while creating very different resource pressure.
• Counting comparisons turns a vague concern about “slowness” into a model: pair-by-pair duplicate detection needs n(n - 1)/2 comparisons in its no-duplicate case.
• A hash-based set commonly changes the expected time shape from O(n²) to O(n) by spending O(n) additional memory.
• Big O compares growth patterns; constants, hardware, input distribution, and implementation still matter for an actual system.
• State the data-structure assumptions and the time-memory trade-off when defending an algorithmic choice.