6. Algorithm Design and Complexity Analysis

Introduction and Context

Programming is not merely the act of writing instructions in a programming language. It is the disciplined process of transforming a problem into a precise, executable, and verifiable procedure. An algorithm is the central intellectual artifact in that process. Programs may be rewritten in different languages, executed on different machines, or deployed in different environments, but the underlying algorithm determines what a system does and how efficiently it does it.

For full-stack developers, algorithmic competence is relevant far beyond academic exercises. A web application may need to search a product catalogue, sort transaction records, traverse a dependency graph, validate nested data, or process millions of log entries. A solution that works for ten records may become unusable for ten million. Consequently, professional programming requires more than functional correctness: it requires reasoning about scalability, resource consumption, maintainability, and evidence from testing and profiling.

This chapter develops methods for designing searching, sorting, traversal, and recursive algorithms. It introduces correctness arguments, edge-case analysis, asymptotic complexity, benchmarking, and profiling. The emphasis is not on memorising isolated algorithms, but on learning how to choose, construct, analyse, and justify them.

Learning Objectives

By the end of this chapter, students should be able to:

1. Express computational problems using clear inputs, outputs, assumptions, and termination conditions.

2. Design and trace linear search, binary search, common sorting algorithms, graph traversals, and recursive procedures.

3. Distinguish correctness, efficiency, robustness, and implementation quality.

4. Analyse time and space requirements using Big-O, Big-Theta, and Big-Omega notation.

5. Identify best-case, average-case, and worst-case behaviour.

6. Handle boundary conditions, invalid input, duplicate values, cycles, and empty structures.

7. Use benchmarking and profiling evidence without confusing empirical results with asymptotic analysis.

8. Select algorithms according to data characteristics, system constraints, and professional requirements.

From Problem Statement to Algorithm

An algorithm should be understood as a finite, unambiguous sequence of steps that transforms valid input into the required output. A strong design begins before code is written. The problem must first be specified in terms of its inputs, outputs, constraints, assumptions, and acceptance conditions.

Consider the problem of finding a customer by account identifier. Relevant questions include the following: Is the data stored in an array, database index, hash table, or tree? Are identifiers unique? Is the data already sorted? Can the collection change during the operation? What should happen when the identifier does not exist? These questions influence both the algorithm and its correctness.

A useful design process is:

• clarify the problem and define the contract;
• identify the data representation and constraints;
• decompose the task into smaller operations;
• select or construct an algorithm;
• establish correctness through reasoning and tests;
• analyse time and space complexity;
• implement, benchmark, and profile;
• review edge cases, maintainability, and operational risks.

A program contract normally contains a precondition, a postcondition, and relevant invariants. The precondition states what must be true before execution. The postcondition states what must be true after successful execution. An invariant is a property preserved during an algorithm's progress.

For example, binary search has the precondition that the input sequence is sorted. Its postcondition is that it returns the position of the target if present and otherwise reports absence. During execution, the search interval remains the only region in which the target could still occur. This interval property is its central invariant.

Correctness Is More Than Producing an Answer

An algorithm is correct if it produces the specified result for every valid input and terminates. Correctness has two closely related dimensions. Partial correctness means that if the algorithm terminates, its result satisfies the specification. Total correctness adds proof of termination.

A practical correctness argument often combines three ideas:

1. Initialization: the invariant is true before the first iteration.

2. Maintenance: each iteration preserves the invariant.

3. Termination: when the loop ends, the invariant and stopping condition imply the desired result.

Suppose a loop scans an array to find the largest value. The invariant can be stated as: after examining the first \(i\) elements, the variable `largest` contains the maximum among those elements. Initially, the first examined element establishes the property. Each subsequent element either leaves `largest` unchanged or replaces it with a larger value. When all elements have been examined, the invariant establishes that `largest` is the maximum of the entire array.

Correctness testing cannot prove an algorithm correct for all possible inputs, but it can reveal defects. Tests should include ordinary cases, empty input, one-element input, duplicate values, already ordered and reverse-ordered data, extreme values, invalid values, and very large inputs. Property-based testing can strengthen this process by generating many inputs and checking general properties, such as whether a sorting algorithm returns an ordered permutation of the original data.

Searching Algorithms

Linear Search

Linear search examines elements sequentially until the target is found or the collection is exhausted. It requires no ordering assumption and is therefore applicable to unsorted arrays and lists.

```text

linearSearch(A, target):

for i from 0 to length(A) - 1:

if A[i] == target:

return i

return NOT_FOUND

```

If the target is at the first position, the best-case time is \(O(1)\). If it is absent or at the final position, the algorithm examines nearly every element, giving worst-case time \(O(n)\). Its auxiliary space is \(O(1)\). Linear search is often appropriate for small collections, unsorted data, or situations in which a single search does not justify preprocessing.

Binary Search

Binary search repeatedly halves a sorted search interval. For an ascending array, the middle element is compared with the target. If the target is smaller, the right portion is discarded; if larger, the left portion is discarded.

```text

binarySearch(A, target):

low = 0

high = length(A) - 1

while low <= high:

mid = low + (high - low) // 2

if A[mid] == target:

return mid

else if A[mid] < target:

low = mid + 1

else:

high = mid - 1

return NOT_FOUND

```

The interval decreases geometrically, so the worst-case time is \(O(\log n)\), with \(O(1)\) auxiliary space in the iterative version. The recursive version also has \(O(\log n)\) stack space. Binary search is not automatically superior: it requires sorted data and efficient random access. Applying it to an unsorted list violates its precondition and can produce an incorrect result.

A common implementation error is calculating the midpoint as `(low + high) / 2` in environments where integer overflow is possible. The safer expression `low + (high - low) / 2` avoids adding two potentially large indices. Other errors include failing to move beyond the midpoint, using incorrect inclusive or exclusive boundaries, and mishandling duplicate values. If the requirement is to find the first occurrence, ordinary binary search must be adapted.

Sorting as an Algorithmic Design Problem

Sorting rearranges values according to an ordering relation. A sorting algorithm may be evaluated by time, auxiliary memory, stability, adaptivity, and whether it operates in place. A stable sort preserves the relative order of records with equal keys. Stability matters when records are sorted successively by multiple fields. An in-place algorithm uses only a small amount of additional storage, although definitions vary regarding recursion and implementation details.

Insertion Sort

Insertion sort builds a sorted prefix one item at a time. Each new item is shifted left until it reaches its correct position. It has worst-case time \(O(n^2)\), but its best-case time is \(O(n)\) when the input is already sorted. It uses \(O(1)\) auxiliary space and is stable in a standard implementation. Its adaptiveness makes it useful for small or nearly sorted collections and as a component within hybrid algorithms.

Selection Sort

Selection sort repeatedly selects the smallest remaining element and places it at the next output position. It performs \(O(n^2)\) comparisons in best, average, and worst cases, and uses \(O(1)\) auxiliary space. It performs relatively few swaps, which can be useful when writing data is expensive, but it is generally less adaptive than insertion sort.

Merge Sort

Merge sort divides a sequence into two halves, recursively sorts the halves, and merges the sorted results. The recurrence is:

\[

T(n) = 2T(n/2) + O(n)

\]

Therefore, its time complexity is \(O(n\log n)\) in the best, average, and worst cases. Standard array-based merge sort uses \(O(n)\) auxiliary space and is stable. Its predictable performance makes it attractive for large data sets and external sorting, where data is processed in blocks that do not fit into memory.

Quicksort

Quicksort selects a pivot, partitions the sequence into elements on either side of the pivot, and recursively sorts the partitions. With balanced partitions, its average time is \(O(n\log n)\). Poor pivot choices can produce partitions of sizes zero and \(n-1\), leading to worst-case \(O(n^2)\) time. Randomised pivots, median-based strategies, and three-way partitioning can reduce the likelihood or impact of poor behaviour, but they do not eliminate the need to understand the worst case.

Quicksort is often fast in practice because of locality and low constant factors. The decision to use it should nevertheless consider recursion depth, duplicate keys, stability requirements, and the quality of the implementation. Production libraries frequently use hybrid algorithms that combine quicksort-like partitioning with insertion sort for small partitions and a worst-case safeguard.

Heap Sort and Library Sorting

Heap sort maintains a heap and repeatedly extracts the maximum or minimum element. It guarantees \(O(n\log n)\) time and uses \(O(1)\) auxiliary space in its in-place form, but it is not normally stable and may have less favourable locality than other methods.

In professional software, a trusted library sort is usually preferable to a handwritten implementation unless educational, specialised, or performance-engineering requirements justify otherwise. The choice should still be informed by the library's documented guarantees, stability, memory behaviour, comparator requirements, and treatment of invalid or incomparable values.

Traversal of Trees and Graphs

Traversal algorithms visit elements of a linked structure systematically. A tree has a hierarchical structure without cycles under its usual definition. A graph may contain cycles, multiple paths, directed edges, and disconnected components. Consequently, graph traversal must maintain a visited set or equivalent marking mechanism when repeated visits could occur.

Breadth-First Search

Breadth-first search (BFS) explores vertices in layers using a queue. Starting from a source, it visits all vertices at distance one, then distance two, and so forth. In an unweighted graph, BFS produces shortest path distances measured in number of edges.

```text

BFS(G, start):

create empty queue Q

mark start visited and enqueue start

while Q is not empty:

v = dequeue Q

process v

for each neighbour u of v:

if u is not visited:

mark u visited

enqueue u

```

With an adjacency-list representation, BFS takes \(O(V+E)\) time and \(O(V)\) auxiliary space, where \(V\) is the number of vertices and \(E\) the number of edges. Marking a vertex when enqueued, rather than when removed, prevents multiple enqueues in typical implementations.

Depth-First Search

Depth-first search (DFS) follows one path as far as possible before backtracking. It can be implemented recursively or with an explicit stack. DFS is useful for cycle detection, connected components, topological ordering, and exploring nested structures.

```text

DFS(v):

mark v visited

process v

for each neighbour u of v:

if u is not visited:

DFS(u)

```

DFS also takes \(O(V+E)\) time with adjacency lists and requires \(O(V)\) space for visited records and, in the worst case, recursion or stack depth. Recursive DFS is clear, but a very deep graph can overflow the call stack. An explicit stack provides greater control in production services.

For a tree, preorder, inorder, and postorder traversals differ in the point at which a node is processed relative to its children. In a binary search tree, inorder traversal produces keys in sorted order, assuming the tree's ordering invariant is maintained.

Recursion: Structure, Proof, and Cost

A recursive algorithm solves a problem by applying itself to smaller instances. Every sound recursive design requires a base case and a recursive case that progresses toward that base case. Without a valid base case, the procedure may not terminate. Without progress, it may repeatedly solve the same problem.

The factorial function illustrates the structure:

```text

factorial(n):

if n == 0:

return 1

return n * factorial(n - 1)

```

For non-negative integers, this has \(O(n)\) time and \(O(n)\) call-stack space. An iterative version has the same time complexity but \(O(1)\) auxiliary space. Recursion is not inherently inefficient; its cost depends on the number and size of subproblems and on the call stack.

Naive recursive Fibonacci computation demonstrates overlapping subproblems. It repeatedly recomputes the same values and has exponential time growth. Memoisation stores previously computed results, reducing the time to \(O(n)\) and requiring \(O(n)\) additional space. This illustrates a general dynamic-programming principle: when subproblems overlap and the problem has an appropriate optimal-substructure property, storing results can replace repeated computation with controlled memory use.

Recurrence relations provide a formal way to analyse recursive algorithms. For example, merge sort's recurrence produces \(O(n\log n)\), while a recurrence of the form \(T(n)=T(n-1)+O(1)\) produces \(O(n)\). The Master Theorem is useful for many divide-and-conquer recurrences, but unusual subproblem sizes, nonuniform costs, or multiple recursive calls may require substitution, recursion-tree analysis, or direct reasoning.

Understanding Complexity Notation

Big-O notation describes an asymptotic upper bound on growth. If an algorithm takes at most a constant multiple of \(f(n)\) for sufficiently large \(n\), it is \(O(f(n))\). Big-Theta describes a tight asymptotic bound, and Big-Omega describes an asymptotic lower bound. In informal software discussions, people often use Big-O to mean the dominant growth rate, but precise analysis should distinguish these meanings.

Common growth rates, from generally more scalable to less scalable, are:

\[

O(1),\quad O(\log n),\quad O(n),\quad O(n\log n),\quad O(n^2),\quad O(2^n),\quad O(n!)

\]

Constants and lower-order terms are ignored in asymptotic analysis. Thus \(3n^2+5n+7\) is \(O(n^2)\), and \(n\log n+n\) is \(O(n\log n)\). This abstraction allows comparison across machines, but it does not predict exact execution time. A linear algorithm with a large constant may outperform a logarithmic algorithm for small inputs, and memory locality, compiler optimisation, input distribution, and language runtime can materially affect results.

Complexity analysis should state what is being measured. Time may refer to comparisons, arithmetic operations, database calls, or total wall-clock time. Space may refer to auxiliary memory, input storage, output storage, or peak resident memory. In a web service, network requests and database queries may dominate CPU complexity, so an algorithmic analysis that ignores I/O can be misleading.

Best-case, average-case, and worst-case analyses answer different questions. Worst-case analysis supports guarantees and capacity planning. Average-case analysis may be useful when a credible input distribution is known. Best-case analysis identifies favourable behaviour but rarely provides a safe operational expectation.

Benchmarking and Profiling: Evidence from Execution

Asymptotic analysis is mathematical reasoning about growth; benchmarking is controlled measurement of actual executions; profiling identifies where an implementation spends time or memory. These approaches complement one another and should not be substituted for one another.

A meaningful benchmark controls or records factors such as input size, input order, data distribution, hardware, runtime version, warm-up effects, compiler optimisation, garbage collection, and system load. It should use representative inputs and repeated trials. Results should be reported with suitable statistics rather than relying on one unusually fast or slow run. For small operations, a benchmark harness may itself introduce significant overhead.

Profiling can be performed through instrumentation, sampling, tracing, memory snapshots, or allocation analysis. A CPU profile may reveal that an apparently efficient sorting function is spending most of its time in an expensive comparator. A memory profile may show that a recursive traversal creates excessive temporary objects. A database trace may demonstrate that the dominant cost lies in repeated queries rather than in the in-memory search algorithm.

Optimisation should follow measurement. A useful workflow is to establish a baseline, identify a bottleneck, form a hypothesis, change one material factor, rerun representative tests, and verify both performance and correctness. Benchmark results should be interpreted cautiously: an improvement on synthetic data may disappear under production workloads, and reducing average latency may worsen tail latency or memory consumption.

Applied Case: Improving Search in an Online Catalogue

Background

This illustrative case concerns an online catalogue service containing product records. The first version loads a collection into memory and searches sequentially by product code for each incoming request.

Situation and Analysis

The service works acceptably during development, but response time increases as the catalogue grows. A review identifies three facts: product codes are unique, the catalogue is periodically rebuilt, and many searches occur between rebuilds. Linear search has \(O(n)\) time per request. Sorting the records once and applying binary search would reduce each search to \(O(\log n)\), but rebuilding the sorted structure has a cost. A hash-based index could provide expected \(O(1)\) lookup, but it would require additional memory and careful handling of updates and collisions.

The team first specifies the contract: a valid code returns exactly one product record; an unknown code returns a not-found response; malformed codes are rejected before lookup. It then tests empty catalogues, one record, duplicate records in input, unknown codes, and rebuilds occurring concurrently with searches.

Approach and Solution

Because the catalogue is rebuilt in batches and searches are frequent, the team constructs an immutable hash index keyed by product code after each successful rebuild. The previous index remains available while the new one is built, and an atomic reference change makes the new version visible. A sorted representation is retained for range queries and ordered display, while the hash index serves exact-match requests.

Benchmarking uses catalogue sizes that reflect anticipated usage and measures median and high-percentile latency, memory consumption, and rebuild time. Profiling confirms that the former linear scan dominated request processing. After the change, lookup cost is substantially less sensitive to catalogue size, although memory usage increases and rebuild operations require validation.

Outcome and Learning Points

The central lesson is that algorithm selection depends on workload, not on an isolated ranking of algorithms. Binary search would have been a substantial improvement over linear search, but the hash index better matched frequent exact-key queries. The solution also demonstrates that correctness includes consistency during updates, not merely returning the right value in a single-threaded test.

Important learning points include:

• a data structure can change the effective complexity of an operation;
• preprocessing is justified when its cost is amortised over many queries;
• benchmarks must represent workload and include memory and tail-latency measures;
• concurrency and update visibility form part of the algorithm's operational contract;
• retaining multiple representations may be appropriate when the application has different query types.

Challenges, Risks, and Common Mistakes

Several errors recur in algorithmic implementations. Treating a sorted-data algorithm as if it worked on arbitrary data is a specification error. Off-by-one errors frequently occur in loops, interval boundaries, and partition procedures. Forgetting to mark graph vertices can cause repeated work or nontermination in cyclic graphs. Recursive procedures may fail because their base cases are incomplete or because input depth exceeds stack capacity.

Complexity claims can also be misleading. Describing a graph algorithm as \(O(V+E)\) without stating the adjacency-list assumption omits an important condition. Reporting average quicksort performance without considering adversarial input may create an operational risk. Ignoring duplicate keys can degrade partitioning. Counting only CPU instructions while excluding database, network, or disk costs can lead to incorrect architectural decisions.

Other risks include integer overflow in index arithmetic, mutation of a collection during traversal, unstable sorting where stability is required, and accepting malformed comparator functions that violate transitivity or consistency. Security-sensitive systems should consider algorithmic denial-of-service attacks, in which crafted inputs trigger excessive time or memory use. Resource limits, input validation, timeouts, and safe library implementations are appropriate safeguards.

Professional and Ethical Considerations

Algorithmic choices affect users, organisations, and infrastructure. Inefficient algorithms can increase operational costs and energy consumption. Incorrect ordering or filtering may disadvantage users, misrepresent information, or produce unfair outcomes in decision-support systems. Developers should document assumptions, validate data quality, and make performance and failure behaviour observable.

When algorithms influence access, ranking, fraud detection, or employment decisions, technical correctness is not sufficient. Teams must consider explainability, bias, privacy, auditability, and human oversight. Profiling and benchmarking data may contain sensitive information and should be handled according to organisational security and privacy policies. Reproducible experiments, code review, versioned dependencies, and documented performance claims support professional accountability.

Contemporary Developments and Best Practices

Modern software increasingly uses hybrid algorithms, parallel processing, vectorised operations, specialised indexes, and distributed data structures. Large-scale data systems may replace in-memory algorithms with external sorting, partitioned processing, caching, or approximate search. Machine-learning systems also use algorithmic techniques for nearest-neighbour search and graph traversal, but these often involve trade-offs between exactness, latency, memory, and update cost.

The following practices provide a reliable professional baseline:

• define the input contract and invariants before implementation;
• choose data structures together with algorithms;
• state preconditions, complexity assumptions, and failure behaviour;
• test boundary cases and properties, not only example outputs;
• prefer mature library implementations when they satisfy requirements;
• benchmark representative workloads and profile before optimising;
• measure memory, throughput, latency, and tail behaviour where relevant;
• review worst-case behaviour and possible adversarial inputs;
• document trade-offs so that future developers can reassess the choice.

Chapter Summary

Algorithm design converts a problem specification into a finite, correct, and efficient procedure. Searching algorithms illustrate the relationship between data assumptions and performance: linear search requires no ordering, while binary search requires sorted data and provides logarithmic search time. Sorting algorithms differ in guarantees, adaptiveness, stability, memory use, and worst-case behaviour. BFS and DFS provide systematic traversal of trees and graphs, with graph complexity commonly expressed as \(O(V+E)\) for adjacency lists. Recursion requires a base case, progress toward that case, and analysis of call-stack cost.

Big-O notation describes asymptotic growth, while benchmarking and profiling provide empirical evidence about implementations. Neither method replaces the other. Robust algorithmic practice combines contracts, invariants, edge-case testing, complexity analysis, representative measurement, and attention to operational, ethical, and security implications. The best algorithm is therefore not simply the one with the smallest theoretical bound; it is the one whose guarantees and trade-offs suit the actual data, workload, constraints, and responsibilities of the system.

Key Terms

Algorithm: A finite, unambiguous procedure for solving a problem.

Asymptotic analysis: Study of resource growth as input size becomes large.

Big-O: An asymptotic upper bound on a function's growth.

Big-Theta: A tight asymptotic bound describing the same growth rate above and below.

Big-Omega: An asymptotic lower bound on growth.

Invariant: A property that remains true during algorithm execution.

Precondition: A condition assumed to hold before an operation begins.

Postcondition: A condition guaranteed after successful execution.

Linear search: Sequential examination of elements until a target is found or input ends.

Binary search: Search by repeatedly halving a sorted search interval.

Stable sorting: Sorting that preserves the relative order of equal-key records.

In-place algorithm: An algorithm using limited additional storage beyond its input.

Recursion: A technique in which a procedure solves smaller instances of itself.

Memoisation: Storing results of solved subproblems to avoid repeated computation.

BFS: Breadth-first graph traversal using a queue.

DFS: Depth-first graph traversal using recursion or a stack.

Benchmarking: Controlled measurement of program performance.

Profiling: Collection of execution data to locate time or memory bottlenecks.

Amortised analysis: Analysis of average cost over a sequence of operations.

Edge case: An input at or near a boundary that may expose implementation defects.

Review Questions

Short Answer Questions

1. What precondition is required for binary search?

2. Distinguish Big-O notation from Big-Theta notation.

3. Why must graph traversal algorithms maintain a visited set?

4. What is the role of an invariant in proving loop correctness?

5. Define a stable sorting algorithm and give one practical reason stability matters.

Long Answer Questions

1. Explain linear search and binary search, including their assumptions, complexity, and appropriate use cases.

2. Compare insertion sort, merge sort, quicksort, and heap sort with respect to time, space, stability, and practical trade-offs.

3. Describe BFS and DFS in detail and explain how their data structures influence their behaviour.

4. Explain how recursion, recurrence relations, and memoisation can be used to analyse and improve algorithms.

5. Discuss how asymptotic analysis, benchmarking, and profiling should be combined in a professional optimisation process.

Analytical / Application Questions

1. A collection is rebuilt once per hour and searched millions of times by unique keys. Compare a sorted-array-plus-binary-search design with a hash-index design, considering preprocessing, memory, updates, and query performance.

2. A DFS implementation works on small graphs but crashes on a very deep graph. Analyse the cause and propose an alternative implementation and testing strategy.

3. A quicksort benchmark is faster than merge sort on random inputs but becomes extremely slow on a particular ordered workload. Explain the likely cause, recommend mitigations, and identify what additional benchmark evidence should be collected.

22. Multiple Choice Questions with Answers

Question 1

Which condition is essential for applying ordinary binary search correctly?

A. The data must contain unique values

B. The data must be sorted according to the search ordering

C. The data must be stored in a linked list

D. The data must contain an even number of elements

Correct Answer: B. The data must be sorted according to the search ordering

Question 2

What is the worst-case time complexity of linear search on an array of n elements?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 3

Which sorting algorithm has O(n log n) worst-case time and is conventionally stable in its array-based implementation?

A. Selection sort

B. Merge sort

C. Naive quicksort

D. Insertion sort

Correct Answer: B. Merge sort

Question 4

Why does BFS find shortest paths in an unweighted graph?

A. It always selects the numerically smallest vertex

B. It explores vertices in nondecreasing number of edges from the source

C. It recursively explores the deepest path first

D. It sorts all edges before traversal

Correct Answer: B. It explores vertices in nondecreasing number of edges from the source

Question 5

For an adjacency-list graph representation, what is the usual time complexity of BFS when all reachable vertices and edges are examined?

A. O(log V)

B. O(V) regardless of edges

C. O(V + E)

D. O(V squared + E)

Correct Answer: C. O(V + E)

Question 6

Which feature is necessary for a recursive algorithm to terminate reliably?

A. A hash table

B. A base case and progress toward it

C. A sorted input

D. A random pivot

Correct Answer: B. A base case and progress toward it

Question 7

An algorithm performs 3n^2 + 5n + 7 operations. What is its asymptotic upper growth classification?

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n^2)

Correct Answer: D. O(n^2)

Question 8

Which statement best distinguishes benchmarking from asymptotic analysis?

A. Benchmarking proves correctness for all inputs

B. Asymptotic analysis measures one machine's wall-clock time

C. Benchmarking measures executions under conditions, while asymptotic analysis studies growth with input size

D. They are identical methods with different names

Correct Answer: C. Benchmarking measures executions under conditions, while asymptotic analysis studies growth with input size

Question 9

A graph contains cycles, and a traversal does not record visited vertices. What is the most likely risk?

A. The traversal may repeatedly visit vertices or fail to terminate

B. The traversal automatically becomes breadth-first

C. The graph becomes sorted

D. The traversal uses no memory

Correct Answer: A. The traversal may repeatedly visit vertices or fail to terminate

Question 10

A catalogue is searched millions of times after being rebuilt in batches. Which design most directly supports expected constant-time exact-key lookup at the cost of additional memory?

A. Repeated linear scans

B. A hash-based index

C. Selection sort before every query

D. Depth-first traversal of an unrelated graph

Correct Answer: B. A hash-based index