Algorithm design develops precise, correct procedures for solving computational problems under meaningful time, memory, input and practical constraints. The work is not choosing the fanciest technique: it begins with a clearly defined question, then a correctness argument and a performance model that match the real decision.
This guide teaches algorithmic thinking through loop invariants, asymptotic analysis, divide and conquer, greedy methods, dynamic programming, graph algorithms and approximation. Worked counterexamples show why a familiar algorithm can fail when an essential assumption or objective changes.
Choose an algorithm design pathway
The objective, proof and growth model · Chapters 1–8 · Start here →
Design paradigms and recurrence thinking · Chapters 9–16 · Start here →
Graph optimisation, sorting and randomisation · Chapters 17–23 · Start here →
Approximation, online decisions and testing · Chapters 24–29 · Start here →
Complete chapter map · Worked algorithms cases · Specialist guide library · Gold Standard master
Complete algorithm-design chapter index
The objective, proof and growth model
Open chapters 1–8
- 1. An algorithm is a solution procedure with obligations
- 2. Algorithm design and data structures are complementary
- 3. Input and output specifications prevent false success
- 4. Correctness has partial and termination components
- 5. Loop invariants explain iterative reasoning
- 6. Big-O records growth, not measured runtime
- 7. Best, average and worst cases ask different questions
- 8. The brute-force baseline provides an honest comparison
Design paradigms and recurrence thinking
Open chapters 9–16
- 9. Divide and conquer splits a problem into smaller instances
- 10. Recurrences connect recursive design to complexity
- 11. Binary search depends on monotonic information
- 12. Greedy algorithms require a structural justification
- 13. A greedy counterexample can be decisive
- 14. Dynamic programming exploits overlapping subproblems
- 15. A small dynamic programming example
- 16. Graph search requires correct edge semantics
Graph optimisation, sorting and randomisation
Open chapters 17–23
- 17. Weighted shortest paths demand matching assumptions
- 18. Minimum spanning trees optimise a different quantity
- 19. Network flow reveals capacity bottlenecks
- 20. Sorting involves stability, space and key definitions
- 21. Comparison-sorting lower bounds have assumptions
- 22. Randomised algorithms need a probability statement
- 23. Amortized complexity is about sequences of operations
Approximation, online decisions and testing
Open chapters 24–29
- 24. Approximation algorithms make limits explicit
- 25. Online algorithms must act without future knowledge
- 26. Streaming algorithms operate under limited memory
- 27. Correctness tests and oracle comparisons
- 28. Trade-offs include fairness, security and maintenance
- 29. Learning pathway and common questions
Select a design approach by the problem structure
| Clue in the problem | Candidate approach | Critical test |
|---|---|---|
| Sorted or monotonic input | Binary search | Monotonicity actually holds |
| Independent smaller instances | Divide and conquer | Base case and combination correct |
| Local choices might be optimal | Greedy | Exchange or other correctness proof |
| Overlapping optimal subproblems | Dynamic programming | State contains enough history |
| Nonnegative weighted paths | Dijkstra | Weights and objective aligned |
| Exact optimum too expensive | Approximation | Feasibility and quality guarantee |
1. An algorithm is a solution procedure with obligations
Algorithm design develops clear, finite procedures for well-defined computational problems and investigates when those procedures are correct and efficient. An algorithm is not merely a piece of code that appears to work on an example. It must define valid inputs, required outputs, acceptable failure conditions and a rule for producing answers.
A route-finding algorithm may need to minimise distance, travel time, financial cost or risk; these are different objectives. Before reaching for a familiar shortest-path routine, state the graph, edge meaning, constraints and intended decision. The best design begins with the right problem rather than a clever technique attached to an ambiguous request.
2. Algorithm design and data structures are complementary
A data structure organises information to support operations such as lookup, insertion or priority selection. An algorithm specifies how operations combine to solve a problem. Dijkstra’s shortest-path algorithm, for example, can use a priority queue, but the queue alone does not establish which distances should be updated or when the answer is final.
The Data Structures guide addresses storage trade-offs; this root focuses on problem formulation, design paradigms, correctness and complexity. Choice of representation still matters to performance, and one must analyse the full algorithm rather than a subroutine in isolation.
3. Input and output specifications prevent false success
A search problem should identify what counts as a valid item, how duplicates are treated, whether order matters and how absence is reported. If an algorithm returns one matching record but users need every duplicate, it can be correctly implemented and still solve the wrong problem. The specification must cover ordinary and boundary cases.
Use a few small examples to clarify the contract before writing code. Ask what happens on empty input, tied scores, invalid identifiers and inaccessible data. For high-consequence settings also specify privacy, fairness and operational constraints; mathematically minimising a chosen cost cannot decide what the cost ought to represent.
4. Correctness has partial and termination components
Partial correctness means that if an algorithm terminates under its preconditions, its result satisfies the postcondition. Total correctness additionally requires that it terminates for all inputs in the specified domain. A loop that eventually would return an accurate answer if it ever ended is not a valid terminating algorithm for the task.
To argue correctness, identify a loop invariant or inductive claim and a progress measure where needed. Testing many inputs is valuable for discovering mistakes, but a general proof must address arbitrary legal cases. See Formal Methods for specifications and stronger verification tools.
5. Loop invariants explain iterative reasoning
A loop invariant is a statement preserved through repeated steps. In insertion sort, a suitable invariant says that the prefix processed so far is sorted and contains exactly the elements originally in that prefix, accounting for the algorithm’s movement. Establish it before the loop, show an iteration preserves it, then use termination to derive a sorted full sequence.
An invariant should be strong enough to imply the goal and precise enough to test against code. ‘The algorithm is nearly correct’ is not an invariant. Draw a five-element trace to expose the rule, then generalise by reasoning about every iteration rather than memorising the trace.
6. Big-O records growth, not measured runtime
Asymptotic notation describes how an upper bound or related rate scales with input size under assumptions. A linear scan of n unsorted items takes O(n) comparisons in the worst case. A binary search on a properly sorted index supports O(log n) comparisons, but maintaining that sorted structure may introduce other work.
An O(n) algorithm can outperform O(log n) for tiny inputs because constants, memory access and preparation differ. State which operation is counted and whether complexity is worst-case, expected or amortized. The mathematical result guides scaling decisions; practical benchmarks check the actual implementation.
7. Best, average and worst cases ask different questions
The best case for a linear search occurs when the desired item is first, while its worst case may inspect every element. An average case requires an explicit model of which inputs or query positions are likely. A single attractive demonstration does not establish the expected cost of a real workload.
For services with deadlines or safety implications, worst-case latency may matter more than average throughput. In other environments expected speed may dominate. Choose the analysis that corresponds to the product requirement and state any probability distribution instead of quietly calling an unspecified scenario typical.
8. The brute-force baseline provides an honest comparison
A straightforward algorithm is often easier to understand and verify. Trying every candidate may be too slow at scale but provides a useful oracle for testing an optimised procedure on small inputs. For choosing the smallest value in an unsorted array, inspecting all relevant values is unavoidable in a general comparison-based model without other information.
Implement a simple correct baseline first when feasible. Measure where it becomes expensive and which structure in the problem might permit improvement. Optimisation without a trustworthy reference can replace a clear correct algorithm with a difficult incorrect one.
9. Divide and conquer splits a problem into smaller instances
Divide-and-conquer algorithms partition input, solve smaller problems and combine results. Merge sort divides a list into halves and merges sorted sublists. Its standard recurrence is T(n)=2T(n/2)+O(n), yielding O(n log n) time under the ordinary model.
The method depends on correct division, base cases and combination. A recursive function that repeatedly calls itself without reducing a measure of the input may never terminate. Analysis should account for copying and memory as well as comparisons.
10. Recurrences connect recursive design to complexity
A recurrence describes the work of smaller recursive calls plus the work done outside them. T(n)=T(n/2)+O(1) models a familiar logarithmic search under suitable assumptions. T(n)=2T(n/2)+O(n) models a different pattern with O(n log n) growth. The difference comes from the number of recursive branches and combine work.
Use recursion trees, induction or a suitable master theorem only when their conditions apply. Include uneven splits and small-input base cases when relevant. An asymptotic formula cannot rescue a recursion that calls itself on unchanged input.
11. Binary search depends on monotonic information
Binary search works when a sorted or otherwise monotonic property lets the algorithm discard half the candidate region after each comparison. It maintains an invariant that any valid answer lies within the remaining interval. For n values, the interval shrinks geometrically, producing logarithmic comparison counts.
Common errors include off-by-one boundaries, incorrect handling of equal values and overflow in midpoint arithmetic in fixed-width integer implementations. A binary-search routine cannot correctly search an unsorted array simply because its code runs fast. Check the predicate’s monotonicity before applying the technique.
12. Greedy algorithms require a structural justification
A greedy algorithm chooses a locally appealing next step, hoping those steps form a globally optimal solution. The approach can be excellent when the problem has a suitable exchange property or matroid-like structure, but local improvement alone is not a proof.
For interval scheduling by maximum number of nonoverlapping intervals, selecting the compatible interval with the earliest finish time is optimal under the standard problem formulation. Selecting the longest or earliest-starting interval need not be. Prove that the chosen first step can be part of an optimal solution, then continue inductively.
13. A greedy counterexample can be decisive
Suppose change-making uses coin values 1,3 and 4 and the goal is to make 6 with the fewest coins. Greedily taking the largest possible coin gives 4+1+1, three coins. The optimal solution is 3+3, two coins. A familiar greedy method for some currency systems fails for this invented denomination set.
The lesson is not that greedy algorithms are generally wrong. It is that their correctness depends on properties of the exact problem, not the appealing idea of making the most progress immediately. Construct small counterexamples before investing in complicated implementation.
14. Dynamic programming exploits overlapping subproblems
Dynamic programming stores solutions to related subproblems so repeated work is avoided. It is useful when the problem has a suitable optimal substructure and overlapping subproblems. Memoisation computes states on demand, while tabulation fills an organised state table in an order that respects dependencies.
Before writing the table, define the state, recurrence, base cases and answer extraction. If a state omits information needed for future decisions, the algorithm may reuse answers in situations that are not equivalent. A large table is not a proof of correctness; its recurrence must correspond to the real choices.
15. A small dynamic programming example
For the minimum coin count with denominations 1,3,4, define dp[x] as the minimum number of coins needed to make amount x. Set dp[0]=0 and for positive x take 1+min dp[x−c] over permitted c≤x. For x=6, the recurrence compares alternatives including dp[3]+1=2.
This identifies two three-value coins rather than a greedy 4+1+1 combination. Correctness follows from considering the last coin of an optimal solution and applying the recurrence to the remainder, given unlimited availability and positive denominations. Change the assumptions and the state may need to change.
16. Graph search requires correct edge semantics
Breadth-first search finds paths with the fewest edges in an unweighted graph. Depth-first search explores along available branches and supports tasks such as cycle detection and topological sorting under suitable conditions. Neither automatically solves weighted shortest paths when edge costs differ.
Represent direction, reachability and edge weights accurately. A road with a missing connection or incorrect travel-time value can invalidate the model even if the search algorithm is correct. Use Graph Theory for graph foundations.
17. Weighted shortest paths demand matching assumptions
Dijkstra’s algorithm solves single-source shortest paths with nonnegative edge weights under its standard formulation. Its greedy finalisation argument relies on not later discovering a lower-cost route through negative edges. Bellman–Ford can handle negative edges and detect relevant negative cycles, though its cost differs.
Choose based on the edge meaning, graph size and available structure. If weights represent capacity or reliability instead of additive cost, ordinary shortest-path arithmetic may answer the wrong question. Analyse the actual path objective before selecting an algorithm.
18. Minimum spanning trees optimise a different quantity
A minimum spanning tree connects all vertices of a connected undirected weighted graph while minimising total selected edge weight. Kruskal’s and Prim’s algorithms exploit cut or cycle properties for correctness. The result is not generally a shortest-path tree from one chosen origin.
Network-planning applications may require redundancy, capacity, forbidden routes or future expansion. A mathematically minimal connecting tree may be a poor real infrastructure design if it lacks resilience. Treat the tree objective as one component of a broader engineering decision.
19. Network flow reveals capacity bottlenecks
Flow algorithms model quantities moving through directed networks subject to capacity and conservation rules. The max-flow/min-cut theorem connects the maximum feasible flow with the capacity of a minimum source–sink cut in the standard model. Its strength is a precise statement about one defined network.
Real systems may need time-dependent scheduling, indivisible commodities, multiple sources or safety restrictions. Do not treat a static max-flow value as proof that a public transport or medical-supply operation will perform at that rate under all conditions. Check how capacity was measured.
20. Sorting involves stability, space and key definitions
A stable sorting algorithm preserves the original relative order of items with equal comparison keys. That property can matter when sorting records first by one field and then another. A sorting method’s time complexity is not the only consideration; memory, worst-case performance and treatment of duplicates also matter.
Define the comparator so it is consistent and supports the intended order. Comparators that contradict transitivity can make some sorting implementations behave unpredictably. A sorted output is only meaningful if the key definition corresponds to the application’s legitimate decision.
21. Comparison-sorting lower bounds have assumptions
Decision-tree reasoning shows that comparison-based sorting of n distinct keys requires Ω(n log n) comparisons in the worst case. This does not forbid faster sorting under additional assumptions about keys. Counting sort and radix sort can achieve different bounds when the key domain and representations permit it.
State the model when citing a lower bound. A theorem about comparison-only operations is not a universal limit for every possible computer and input representation. Knowing exactly what is impossible under an assumption prevents both exaggerated claims and unnecessary optimisation.
22. Randomised algorithms need a probability statement
Some algorithms use random choices to improve expected performance or simplify design. The guarantees may concern expected running time, failure probability or both, depending on the method. Randomised quicksort has expected O(n log n) comparison complexity under its familiar pivot strategy, though a poor pivot sequence can yield quadratic work.
Report which guarantee is random and what probability model is assumed. A random seed can make testing reproducible, but it does not remove inherent worst-case possibilities. Critical systems may need deterministic fallbacks or carefully bounded risk rather than relying on the average of attractive runs.
23. Amortized complexity is about sequences of operations
Amortized analysis bounds the cost per operation across a sequence without requiring a probability distribution. Dynamic-array capacity doubling and certain disjoint-set structures are standard examples. An occasional expensive step is paid for by a long history of cheaper operations in the analysis.
Amortized constant time is not the same as a worst-case response-time guarantee. If one request must finish within a hard deadline, an operation that occasionally copies a huge array may be unacceptable. Identify which kind of performance promise the user or system needs.
24. Approximation algorithms make limits explicit
When an exact optimisation problem is computationally difficult, an approximation algorithm may find a feasible answer with a provable quality bound under specified assumptions. For a minimisation problem, an approximation ratio can compare the computed cost with the optimal cost, though definitions and conditions vary.
The guarantee is not a moral licence to accept any approximate decision. If an error changes a medical or legal outcome, different constraints apply. Define the objective, feasibility requirements and consequences of approximation before using a theoretical performance factor as a product promise.
25. Online algorithms must act without future knowledge
An online algorithm receives information over time and must make decisions before seeing all future requests. Scheduling and caching are familiar examples. Competitive analysis compares an online algorithm’s performance with a defined offline benchmark that may know the full sequence, under carefully stated rules.
A decision that looks poor with hindsight may have been reasonable given information actually available. Record what the algorithm knew at each step and how updates affect prior commitments. An offline optimal result should not be misrepresented as a feasible real-time policy.
26. Streaming algorithms operate under limited memory
Streaming algorithms process large or rapid data sequences without retaining every input. They may maintain counters, samples, sketches or approximate summaries. Such methods can be valuable for telemetry and large datasets, but different summaries have different error guarantees and update assumptions.
A compact sketch estimating distinct items may not identify which exact records are present, and approximate frequency counts can mislead if presented as exact. Report error probabilities, bounds and the required memory. Real-time performance is useful only when measurement and interpretation remain trustworthy.
27. Correctness tests and oracle comparisons
A brute-force reference can verify optimised algorithms on small instances. Property-based tests can check invariants such as sortedness, preservation of elements, valid path costs or conservation of flow. Metamorphic tests examine predictable relationships under controlled input changes when exact answers are hard to compute.
Do not treat random tests as a universal proof. For critical invariants, use reasoning, model checking or other formal tools where justified. Explain what was exercised and what remains beyond the tested size and operating conditions.
28. Trade-offs include fairness, security and maintenance
Algorithm design choices affect people through the objective, input coverage and update rules. An algorithm that minimises total waiting time may still impose unacceptable delays on a small group. A model that predicts risk can become harmful if its labels are used to deny opportunities without review.
State service requirements and stakeholder consequences alongside asymptotic complexity. Avoid collecting unnecessary personal data and test unexpected workloads and adversarial inputs. A fast algorithm solving an unethical or mis-specified objective is not a gold-standard solution.
29. Learning pathway and common questions
Begin with a precisely defined task such as finding a duplicate, schedule or shortest path. Implement a simple baseline, trace boundary cases and write an invariant. Then learn divide and conquer, greedy exchange arguments and dynamic programming recurrences. At advanced level include complexity bounds, randomisation and resource constraints.
Does O(log n) always beat O(n)? Not on every real input or machine. Is dynamic programming merely recursion? No; it relies on a structured reuse of subproblem answers. Does greedy always work? No. Is an efficient algorithm automatically correct? No. The standard is an explicit objective, justified method and honest performance evidence.
Sixteen algorithm-design diagnosis and worked calculations
1. A binary search on unsorted data
A list contains 3,9,2,10,4. A binary search routine assumes monotonic order, discards half the values and may miss a valid target. The code’s asymptotic analysis is irrelevant until its precondition is satisfied. Sort or use another search strategy, and include a test that detects invalid ordering.
2. A greedy change-making counterexample
With coin values 1,3,4, making 6 by greedily selecting the largest coin gives 4+1+1, three coins. The optimal solution 3+3 uses two. The example disproves a universal claim that this greedy rule minimises coin count for all denominations.
3. Correct loop invariant for maximum search
An array scan tracks best-so-far. After processing the first k values, the invariant is that best equals the maximum among those k values. Initialisation, update and termination together justify the result on any nonempty legal input. The empty case needs an explicit contract.
4. Two recurrences with different answers
A recursive process with T(n)=T(n/2)+1 has logarithmic depth under standard assumptions. Merge-sort-like T(n)=2T(n/2)+n has O(n log n) growth. Both halve input size, but the number of recursive calls and the combination cost differ.
5. A dynamic programming state omits a quota
A scheduling algorithm stores only the day and remaining time, but the rules allow each worker at most two shifts. Two states with the same day and time may differ by shifts already used, so memoising them as identical can produce invalid schedules. Expand the state or redesign the recurrence.
6. An interval scheduling greedy choice
Three intervals are [1,10], [2,3] and [4,5]. Choosing the earliest-starting interval [1,10] admits only one activity, while choosing by earliest finish time allows [2,3] and [4,5]. The local rule needs a proof relevant to the exact objective.
7. A negative edge violates Dijkstra’s premise
A directed graph includes a negative-cost edge. Standard Dijkstra reasoning relies on nonnegative weights and may finalise a distance too early. Use an algorithm suitable for the graph and consider whether the cost model allows negative cycles that make a finite shortest path undefined.
8. Fewest edges versus lowest cost
Path A→B→D has two edges costing twelve minutes; A→C→E→D has three edges costing eight. BFS by edge count returns the former, but the travel-time objective prefers the latter. State edge units before using a search method.
9. MST does not minimise every origin path
A tree connecting all sites at minimum total cable length may route one remote site’s data along a long chain. A shortest-path tree from the main centre solves a different objective and can use different edges. Specify which cost the project actually needs.
10. A comparator contradicts itself
A sorting comparator says A precedes B, B precedes C and C precedes A. This violates transitivity and undermines the ordering contract on which a sorting algorithm relies. Check comparator rules, especially with approximate numeric equality or locale-sensitive text.
11. A lower bound used outside its model
A claim that sorting always needs Ω(n log n) time is made without noting the comparison model. If keys are small bounded integers, counting-based methods may achieve different bounds. Always state the computational model and assumptions behind an impossibility or lower-bound theorem.
12. A random pivot yields one bad run
Randomised quicksort usually performs efficiently in expectation under the pivot-selection model, but one unfortunate sequence can produce poor partitions. A single slow run neither invalidates the expected bound nor satisfies a hard latency guarantee. Evaluate distributions and worst-case risks separately.
13. A streaming estimate is presented as an exact count
A compact sketch estimates the number of distinct visitors. Reporting that estimate as an exact integer without an uncertainty bound can mislead. Explain the hash assumptions, error properties and appropriate denominator; use exact counting if the decision truly requires an exact result.
14. An online strategy cannot see a future request
A cache replacement algorithm evicts an item that later becomes popular. A hindsight-optimal policy would have retained it, but the online algorithm did not know the future. Compare policies using a correctly defined online benchmark and actual information available at each decision.
15. An approximate solution violates a hard constraint
A route planner finds a nearly optimal path in total distance but passes through an area forbidden by a safety rule. Feasibility is not a soft optional objective. Design the approximation within hard constraints, then measure quality among valid solutions.
16. A very fast result answers the wrong question
A school allocates tutorials to minimise administrative cost but ignores prerequisite need and accessibility. The optimisation algorithm may be correct for that objective while producing poor educational decisions. Rewrite the specification with appropriate constraints and stakeholder review before benchmarking speed.
Explore the connected eduKate Gold Standard library
Algorithms, structures and formal reasoning
Application and validation
Authoritative algorithm courses and textbooks
- MIT OpenCourseWare — 6.006 Introduction to Algorithms
- MIT OpenCourseWare — 6.046J Design and Analysis of Algorithms
- Stanford University — CS161 Design and Analysis of Algorithms
- Stanford CS161 — Course Materials and Problem-Solving
- Princeton University — Algorithms, Fourth Edition companion site
All algorithms, numbers and application cases are illustrative. A mathematical performance bound does not establish that an untested production implementation meets safety, privacy, fairness or operational commitments.
Sixteen additional algorithm design and changed-objective challenges
These hypothetical exercises test the assumptions behind correctness proofs, complexity bounds and optimisation goals. A familiar algorithm should be reused only when its input conditions and decision objective are still the right ones.
1. The optimisation target omits a legal constraint
A delivery planner minimises distance but sends a vehicle through a road with a weight restriction. The shortest route is not a feasible route under the actual problem. Represent forbidden edges or route states before running optimisation, and verify that every returned path satisfies safety and regulatory constraints. If the real objective also includes delivery windows, state those constraints explicitly. An algorithm can be fast and mathematically correct for a graph while failing the legal and operational problem its users need solved.
2. One extra condition breaks a greedy scheduling proof
The classical earliest-finish-time strategy selects a maximum-size set of compatible unweighted intervals. Now each activity has a different benefit, and the objective changes to maximum total benefit rather than maximum count. Choosing the earliest end can discard one longer activity worth more than several shorter ones. The earlier exchange proof no longer establishes optimality for the new objective. Reframe the problem as weighted interval scheduling and use an appropriate dynamic programming recurrence. Transfer requires preserving what the theorem actually assumed.
3. A baseline oracle exposes a subtle dynamic-programming bug
A proposed optimisation solves minimum-coin problems using a state table, but its recurrence permits an amount smaller than zero and uses a default value of zero for missing states. The resulting answer can appear better than the true optimum. For amounts up to a small bound, compare against exhaustive enumeration that respects each coin’s availability. Correct base cases and invalid states, then prove the recurrence’s structure. A simple trusted baseline is valuable even when it cannot scale to the full production input.
4. A shortest-path request with time-dependent edges
A train graph represents direct routes, and edge weights store average travel duration. The traveller needs to leave at 20:00, when some services no longer run. A static minimum-weight algorithm can produce a connection sequence that is impossible to board. Represent departure schedules, waiting time and permitted transfers, then choose an appropriate time-dependent algorithm. The path objective should be arrival time or another real measure rather than merely adding incompatible average edge weights. Correct graph algorithms do not repair incorrect network representation.
5. A recursion stops on odd sizes but not even ones
A divide-and-conquer routine splits n into subproblems and returns only when n=1. On n=0, it recursively splits into another zero-length subproblem, never making progress. If empty input is legal, add the appropriate base case and prove the measure decreases for every non-base step. Also check rounding when n is odd. A recurrence analysis assumes termination structure, so it cannot justify the run time of a defective recursion with an unhandled boundary.
6. The sorting comparator changes under deployment
A school information service sorts mixed numeric identifiers as text, placing ‘100’ before ’20’ under lexicographic ordering. The sorting algorithm works correctly for its comparator, but users expect numeric ordering while leading zeros must still be preserved as part of some identifiers. Decide whether the fields are numerical quantities or symbolic codes, define comparison semantics, and test real records. The correct key definition is a requirement, not a performance optimisation. This matters before choosing mergesort, heapsort or any other procedure.
7. An approximate optimum hides a distributional cost
An allocation algorithm reduces total waiting time by 15% in an invented simulation, but the longest wait for a small group triples. The optimisation objective may be satisfied while an important fairness or service constraint is violated. Report aggregate and relevant subgroup outcomes, include hard limits if required, and review who bears the costs. A theoretical approximation ratio applies to the chosen objective, not to every ethical or operational consequence of the decision. Improve the specification rather than blaming the search algorithm for pursuing the stated target.
8. The algorithm’s expected cost depends on its input model
An algorithm is described as fast on average because keys are assumed uniformly distributed. In actual use, many requests target a small set of popular values, and observed latency differs from the paper’s expected cost. Re-evaluate distributions, collision behaviour and cache effects. Expected complexity is a conditional mathematical claim, not a guarantee about any workload called typical. Profiling can reveal the gap, while rigorous analysis explains which assumption changed. Document both instead of replacing one unsupported average with another.
9. A negative cycle makes the route objective undefined
Suppose a graph permits a cycle whose total weight is negative, and a path can pass through it repeatedly before reaching a destination. Under an unrestricted additive shortest-walk model, the cost can decrease without bound, so there is no finite minimum. Algorithms such as Bellman–Ford can detect relevant reachable negative cycles. Before selecting the solver, clarify whether paths may revisit nodes and what negative weights mean. If the application represents physical travel time, negative edges themselves may indicate an invalid modelling choice.
10. A decision tree lower bound is used as a runtime guarantee
A comparison-sorting lower bound shows no algorithm can beat Ω(n log n) comparisons in the worst case under the standard model. A developer treats that lower bound as proof that a particular sort runs in O(n log n). The two statements have different directions. To establish an upper bound, analyse the chosen algorithm’s own steps or give a relevant theorem. Lower bounds identify necessary work for a class of algorithms; they do not certify the performance of an arbitrary implementation. Keep upper and lower bound claims distinct.
11. A cache algorithm has a misleading offline competitor
A streaming service compares its online replacement policy with a benchmark that knows every future request. The online policy looks worse, which may be inevitable without future information. Competitive analysis can quantify the gap under a defined model, but real operational review should also compare feasible alternatives using information genuinely available at decision time. State the benchmark’s capabilities and the meaning of the score. It is misleading either to hide a hindsight advantage or to pretend an offline optimum can simply be deployed as a real-time algorithm.
12. A streaming sketch cannot support individual verification
A compact estimator reports approximately 40,000 unique events in a stream under its assumptions. An administrator asks whether a particular named record was present. The sketch may not retain exact membership information. Use an authoritative event store or another suitable structure for that question; do not infer individual attendance from an aggregate approximation. Define the target accuracy, privacy obligations and memory budget. An algorithm useful for population-scale monitoring may not provide evidence sufficient for personal or high-stakes decisions.
13. A graph traversal silently changes node identity
An educational collaboration graph merges two people whose display names match, then computes connected components. The traversal algorithm is correct for the merged graph but the network itself is wrong. Stable, privacy-appropriate identifiers and deduplication rules are part of the input specification. A mathematically correct reachability result cannot establish a real relationship when record identity was misassigned. Audit graph construction separately from graph traversal, and disclose missing participants or links before interpreting social structure.
14. Algorithmic randomisation is not a research randomised trial
A route optimiser chooses random seeds during its internal search. A project report describes this as a randomised experiment proving the route policy causes fewer delays. Randomness inside an algorithm is not assignment of comparable real units to intervention conditions. Causal evaluation would need a separate design controlling alternative explanations and measuring outcomes. Distinguish an algorithm’s randomness from experimental randomisation. The first helps explore a computational search space; the second can help identify an effect under suitable research assumptions.
15. A theoretical speedup consumes too much memory
A dynamic programming method converts exponential recomputation into polynomial-time table filling, but the table requires more memory than the deployment hardware has. Identify which states are needed at once, whether rolling arrays or sparse memoisation can reduce storage, and whether an alternative approach is suitable. Optimising runtime alone is not enough. A practical algorithm must fit both time and space constraints and provide a defined failure mode when resource limits are reached. Benchmark realistic upper bounds before deployment.
16. A correctness proof assumes an unavailable oracle
A proposed algorithm makes repeated calls to a subroutine described as instantly identifying the true best allocation. If that subroutine is itself the difficult problem, the design has not solved the computational challenge. Specify each oracle’s operations and implementation cost, including preprocessing. A valid reduction is useful when it transforms a hard problem into one that can genuinely be solved with available tools. Hiding complexity behind an undefined helper is neither a proof of efficiency nor a working procedure.
Return to The Gold Standard, Education and Learning Transfers into Life, or How X Works.