Algorithms, Asymptotic Analysis and Computational Complexity

Introduction

Algorithms are systematic procedures for solving problems. They are central to computer science because a program is, in essence, an implementation of an algorithm expressed in a programming language. In artificial intelligence and machine learning, algorithms determine how data are searched, transformed, optimized, classified, and learned from. The quality of an algorithm depends not only on whether it produces correct results, but also on how efficiently it uses time, memory, communication, and other computational resources.

This chapter develops a framework for expressing algorithms precisely, proving that they work, estimating their resource requirements, and classifying problems according to their computational difficulty. It introduces asymptotic notation, recurrence relations, common algorithmic paradigms, and the distinction between tractable, intractable, and NP-complete problems.

Learning Objectives

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

1. Describe algorithms using precise pseudocode and appropriate abstractions.

2. Explain and apply loop invariants and mathematical induction to establish correctness.

3. Analyze worst-case, average-case, and best-case time and space complexity.

4. Use Big-O, Big-Theta, and Big-Omega notation correctly.

5. Solve simple recurrence relations and compare common growth rates.

6. Recognize divide-and-conquer, greedy, dynamic-programming, and backtracking approaches.

7. Distinguish tractable, intractable, NP, NP-hard, and NP-complete problems.

8. Evaluate algorithmic choices in AI and professional computing contexts.

1. What Is an Algorithm?

An algorithm is a finite, definite, and effective sequence of operations that transforms valid input into the required output. The principal properties are:

• Input: It accepts zero or more clearly specified values.
• Output: It produces at least one result relevant to the problem.
• Definiteness: Every step is unambiguous.
• Finiteness: It terminates after a finite number of steps for every valid input.
• Effectiveness: Each step can be carried out mechanically using available computational operations.
• Correctness: It produces the specified output for every input in its domain.

An algorithm is not the same as a program. An algorithm is a language-independent method; a program is a particular implementation. The same binary-search algorithm may be implemented in Python, Java, or C++, while retaining the same essential structure.

1.1 Problem specifications

Before designing an algorithm, define:

• the input domain;
• the required output;
• assumptions and constraints;
• exceptional cases;
• acceptable resource limits.

For example, “find the largest value in a list” requires clarification about whether the list may be empty, whether values are numeric, and whether modifying the list is allowed. A precise specification might be: given a nonempty finite sequence of real numbers, return its maximum element without changing the sequence.

1.2 Pseudocode conventions

Pseudocode communicates logic without committing to a programming language. A useful style uses indentation, meaningful names, assignment arrows, conditionals, loops, and explicit returns.

```text

LINEAR-SEARCH(A, target)

for i ← 1 to length(A) do

if A[i] = target then

return i

return NOT-FOUND

```

The algorithm returns an index when the target occurs and `NOT-FOUND` otherwise. Its behavior is independent of any particular programming language.

2. Correctness of Algorithms

An algorithm is correct if it satisfies two conditions:

1. Partial correctness: Whenever the algorithm terminates, its output satisfies the specification.

2. Termination: The algorithm terminates for every valid input.

Together, these establish total correctness.

2.1 Loop invariants

A loop invariant is a statement that remains true before and after every iteration of a loop. A standard proof has three parts:

• Initialization: Show that the invariant is true before the first iteration.
• Maintenance: Show that if it is true before an iteration, it remains true after that iteration.
• Termination: Show that when the loop ends, the invariant and the stopping condition imply the desired result.

Worked Example: Maximum of an Array

```text

MAXIMUM(A)

max ← A[1]

for i ← 2 to length(A) do

if A[i] > max then

max ← A[i]

return max

```

Invariant: Before each iteration with index `i`, `max` is the largest element among `A[1], ..., A[i−1]`.

• Initialization: Before the first iteration, `i = 2`, and `max = A[1]`; therefore the invariant holds.
• Maintenance: If `max` is the largest value in the processed prefix, comparing it with `A[i]` and retaining the larger value makes it the largest value in `A[1], ..., A[i]`.
• Termination: After the final iteration, every element has been processed, so `max` is the largest element in the entire array.

Because the loop has a finite number of iterations, it terminates. Thus the algorithm is totally correct.

2.2 Mathematical induction

Induction is particularly useful for recursive algorithms and statements indexed by input size. To prove a proposition `P(n)` for all integers `n ≥ n₀`:

1. Prove the base case `P(n₀)`.

2. Assume `P(k)` is true for an arbitrary `k ≥ n₀`.

3. Use that assumption to prove `P(k+1)`.

For recursive algorithms, the induction hypothesis often states that the algorithm is correct for smaller inputs, which supports correctness on the current input.

2.3 Termination arguments

Termination can be shown using a ranking function or variant: a nonnegative quantity that strictly decreases on every iteration. For example, in a loop that repeatedly removes one item from a finite set, the set size decreases and cannot decrease indefinitely.

3. Measuring Algorithmic Efficiency

Efficiency is evaluated as a function of input size, usually denoted by `n`. Input size must be defined appropriately. For an array, `n` is commonly its number of elements. For a graph, it may be described using vertices `V` and edges `E`. For an integer, the relevant size is often its number of bits, not its numerical value.

Two main resources are:

• Time complexity: The number of elementary operations or computational steps.
• Space complexity: The additional memory required during execution, excluding or including input storage depending on the stated convention.

Complexity analysis generally ignores machine-specific constants and focuses on growth as input size increases.

3.1 Best, worst, and average cases

The best-case complexity is the minimum resource use over inputs of size `n`. The worst-case complexity is the maximum. The average-case complexity is the expected resource use under a specified probability distribution over inputs.

Worst-case analysis is often preferred for guarantees. Average-case analysis can be more representative, but it requires a defensible input distribution. A claim such as “the average running time is linear” is incomplete unless the meaning of average is stated.

4. Asymptotic Notation

Asymptotic notation describes growth for sufficiently large input sizes. Let `f(n)` and `g(n)` be nonnegative functions for sufficiently large `n`.

4.1 Big-O notation

`f(n) = O(g(n))` if there exist constants `c > 0` and `n₀` such that

`0 ≤ f(n) ≤ c g(n)` for all `n ≥ n₀`.

Big-O is an asymptotic upper bound. If an algorithm takes `3n² + 5n + 7` operations, it is `O(n²)`. Constants and lower-order terms do not affect the dominant growth rate.

4.2 Big-Omega notation

`f(n) = Ω(g(n))` if there exist constants `c > 0` and `n₀` such that

`0 ≤ c g(n) ≤ f(n)` for all `n ≥ n₀`.

This is an asymptotic lower bound. A comparison-based sorting algorithm requires `Ω(n log n)` comparisons in the worst case under the standard comparison model.

4.3 Big-Theta notation

`f(n) = Θ(g(n))` if there exist positive constants `c₁`, `c₂`, and `n₀` such that

`0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)` for all `n ≥ n₀`.

Theta notation gives a tight asymptotic bound. Since `3n² + 5n + 7` is both `O(n²)` and `Ω(n²)`, it is `Θ(n²)`.

4.4 Common growth rates

For sufficiently large `n`, the usual ordering is:

`1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!`.

The base of a logarithm does not affect its asymptotic class because changing bases multiplies the logarithm by a constant. In algorithm analysis, logarithms are commonly assumed to have base 2.

Worked Example: Counting Operations

```text

COUNT-PAIRS(A)

count ← 0

for i ← 1 to n do

for j ← 1 to n do

count ← count + 1

return count

```

The inner statement executes once for every ordered pair `(i, j)`, giving exactly `n × n = n²` executions. Therefore the running time is `Θ(n²)`. The variables `i`, `j`, and `count` use constant extra space, so auxiliary space is `Θ(1)`.

4.5 Rules for combining complexities

Sequential parts add their costs. If one part takes `Θ(n)` and another takes `Θ(n²)`, their total is `Θ(n + n²) = Θ(n²)`.

Nested loops often multiply iteration counts. If an outer loop executes `n` times and an inner loop executes `n` times per outer iteration, the result is `Θ(n²)`. However, loop bounds must be examined carefully; a loop whose index doubles each time has logarithmic, not linear, iterations.

5. Analysis of Representative Algorithms

5.1 Linear search

Linear search examines items sequentially. In the worst case, it examines all `n` elements, so its time complexity is `Θ(n)`. If the target is equally likely to be at any position and is guaranteed to occur, the expected number of comparisons is `(n+1)/2`, which is `Θ(n)`. Its auxiliary space is `Θ(1)`.

5.2 Binary search

Binary search requires a sorted array. At each step it compares the target with the middle element and discards half of the remaining search interval.

```text

BINARY-SEARCH(A, target)

low ← 1

high ← length(A)

while low ≤ high do

mid ← low + floor((high − low) / 2)

if A[mid] = target then

return mid

else if A[mid] < target then

low ← mid + 1

else

high ← mid − 1

return NOT-FOUND

```

After `k` iterations, the remaining interval is approximately `n/2ᵏ`. The process ends when this is at most 1, so `k` is proportional to `log₂ n`. The worst-case time is `Θ(log n)`, and the iterative version uses `Θ(1)` auxiliary space. The requirement that the data be sorted is essential.

5.3 Selection sort

Selection sort repeatedly selects the smallest remaining item and places it in the next position. It performs approximately `n(n−1)/2` comparisons, giving `Θ(n²)` time in best, average, and worst cases. It uses `Θ(1)` auxiliary space and is useful mainly for small datasets or situations where simplicity and minimal extra storage matter.

5.4 Merge sort

Merge sort uses divide and conquer:

1. Divide the array into two halves.

2. Recursively sort each half.

3. Merge the two sorted halves.

The recurrence is

`T(n) = 2T(n/2) + Θ(n)`, with `T(1) = Θ(1)`.

At each recursion level, merging costs `Θ(n)`, and there are `Θ(log n)` levels. Hence `T(n) = Θ(n log n)`. Standard array-based merge sort requires `Θ(n)` auxiliary space. Its predictable worst-case performance makes it valuable when guaranteed sorting time is important.

5.5 Quicksort

Quicksort selects a pivot, partitions elements around it, and recursively sorts the two partitions. If partitions are balanced, its recurrence resembles

`T(n) = 2T(n/2) + Θ(n)`,

giving `Θ(n log n)`. If the pivot repeatedly produces partitions of sizes 0 and `n−1`, the recurrence becomes

`T(n) = T(n−1) + Θ(n)`,

giving `Θ(n²)`. Randomized pivot selection makes consistently poor partitions unlikely, and the expected running time is `Θ(n log n)`, although the worst-case bound remains `O(n²)` for common implementations. Quicksort often has excellent practical performance because partitioning can be performed largely in place.

6. Recurrences and the Master Theorem

Recursive algorithms are often analyzed using recurrences. A common form is

`T(n) = aT(n/b) + f(n)`,

where `a ≥ 1` is the number of recursive subproblems, each has size `n/b` with `b > 1`, and `f(n)` is the nonrecursive work.

The Master Theorem compares `f(n)` with `n^{log_b a}`:

• If `f(n) = O(n^{log_b a − ε})` for some `ε > 0`, then `T(n) = Θ(n^{log_b a})`.
• If `f(n) = Θ(n^{log_b a} log^k n)` for `k ≥ 0`, then `T(n) = Θ(n^{log_b a} log^{k+1} n)`.
• If `f(n) = Ω(n^{log_b a + ε})` for some `ε > 0`, together with a regularity condition, then `T(n) = Θ(f(n))`.

For merge sort, `a=2`, `b=2`, and `f(n)=Θ(n)`. Since `n^{log₂2}=n`, the second case gives `Θ(n log n)`.

The theorem does not apply automatically to every recurrence. Unequal subproblem sizes, non-polynomial terms, and failure of the regularity condition may require recursion trees, substitution, or other methods.

7. Algorithm Design Paradigms

7.1 Divide and conquer

Divide-and-conquer algorithms divide a problem into smaller independent subproblems, solve them recursively, and combine their results. Merge sort and binary search are standard examples. The approach is effective when subproblems are similar and the combination step is manageable.

7.2 Greedy algorithms

A greedy algorithm repeatedly makes the locally best choice, hoping that local choices form a globally optimal solution. Greedy methods are correct only when the problem has appropriate structure, such as the greedy-choice property and optimal substructure.

For example, Kruskal’s algorithm constructs a minimum spanning tree by repeatedly selecting the least-weight edge that does not create a cycle. Its correctness follows from the cut property of minimum spanning trees, not merely from the intuition that inexpensive edges are generally desirable.

7.3 Dynamic programming

Dynamic programming applies when a problem has:

• Optimal substructure: An optimal solution contains optimal solutions to relevant subproblems.
• Overlapping subproblems: The same subproblems occur repeatedly.

It stores solutions to subproblems using memoization (top-down) or tabulation (bottom-up). The 0/1 knapsack problem, sequence alignment, and many shortest-path problems can be treated this way.

Dynamic programming may reduce exponential recursive computation to polynomial time, but the table can require substantial memory. The time and space costs depend on the dimensions and numerical representation of the state.

7.4 Backtracking and branch-and-bound

Backtracking explores a space of candidate solutions and abandons a partial candidate as soon as it violates a constraint. It is useful for constraint satisfaction, such as Sudoku or the n-queens problem. In the worst case, its search may remain exponential.

Branch-and-bound adds bounds that estimate whether a partial solution can improve the best known solution. It can be highly effective in practice, but a good practical performance does not imply a polynomial worst-case bound.

8. Computational Complexity and Problem Classes

Algorithm complexity concerns the resources used by a particular algorithm. Computational complexity theory also studies the intrinsic difficulty of problems: whether any algorithm can solve them efficiently under a chosen computational model.

8.1 Tractable and intractable problems

A problem is commonly called tractable when it has a polynomial-time algorithm, such as `O(n)`, `O(n²)`, or `O(n^k)` for a fixed constant `k`. Polynomial time is considered a practical boundary in theory because polynomial growth is generally more manageable than exponential growth, although a high-degree polynomial may still be unusable in practice.

An intractable problem is one for which known exact algorithms require superpolynomial time, or which is believed not to have a polynomial-time algorithm. This term must be used carefully: “intractable” may refer to practical difficulty, theoretical lower bounds, or the absence of known efficient algorithms.

8.2 Decision and optimization problems

A decision problem has a yes/no answer. For example:

> Given a graph and integer `k`, does the graph contain a clique of at least `k` vertices?

An optimization problem asks for the best solution, such as the largest clique. Complexity classes are usually defined using decision problems because yes/no verification is mathematically convenient.

8.3 The class P

`P` is the class of decision problems solvable by a deterministic algorithm in polynomial time with respect to input length. Sorting is not itself a decision problem, but questions such as “does the array contain a duplicate?” can be solved in polynomial time and therefore belong to `P`.

8.4 The class NP

`NP` is the class of decision problems for which a proposed yes-certificate can be verified in polynomial time by a deterministic algorithm. Equivalently, NP is the class solvable in polynomial time by a nondeterministic Turing machine.

The certificate must have polynomial length, and verification must be polynomial in the input length. For the Hamiltonian-cycle decision problem, a proposed ordering of vertices is a certificate; one can verify in polynomial time that each consecutive pair forms an edge and that every vertex is used exactly once.

It is known that `P ⊆ NP`, because a polynomial-time solver can also verify a solution. Whether `P = NP` remains an open question.

8.5 NP-hard and NP-complete

A problem is NP-hard if every problem in NP can be transformed to it using a polynomial-time reduction. An NP-hard problem need not itself belong to NP; it may be an optimization problem or even undecidable in broader settings.

A problem is NP-complete if it is both:

1. in NP; and

2. NP-hard.

Examples include Boolean satisfiability (SAT), 3-SAT, the decision version of the travelling-salesperson problem, and the decision version of the clique problem.

8.6 Polynomial-time reductions

To show that problem `A` is at least as difficult as problem `B`, a common approach is to transform instances of `B` into instances of `A` in polynomial time. If solving `A` efficiently would solve `B` efficiently, then `B ≤ₚ A`. To prove that `A` is NP-hard, reduce a known NP-complete problem to `A`, not the reverse.

A frequent reasoning error is to show only that a problem can be transformed into an easy problem. That does not establish hardness. The direction of the reduction is essential.

9. AI and Machine-Learning Applications

Algorithmic analysis is directly relevant to AI systems:

• Search: Breadth-first search is `O(V+E)` for a graph represented by adjacency lists, where `V` is the number of vertices and `E` the number of edges. Uninformed search may nevertheless require exponential space in the depth of a search tree.
• Sorting and preprocessing: Data preparation can dominate the cost of model training when datasets are large.
• Nearest-neighbor methods: Exact search may be expensive in high-dimensional spaces, motivating indexing and approximate nearest-neighbor algorithms.
• Optimization: Training algorithms trade convergence speed, memory, numerical stability, and parallelism.
• Inference: A model may have acceptable training complexity but unacceptable latency or memory requirements in deployment.
• Combinatorial AI: Scheduling, routing, assignment, and planning frequently contain NP-hard components, requiring heuristics, approximation, relaxation, or restricted problem structures.

Big-O analysis is necessary but not sufficient for AI engineering. Constants, cache behavior, hardware acceleration, data distribution, parallelism, numerical precision, and communication costs can determine actual performance.

10. Applied Case Study: Route Planning for a Delivery Service

This is an illustrative case study.

Background

A delivery company must plan routes for vehicles serving many customer locations. It seeks to minimize total distance while respecting vehicle capacity and delivery-time constraints.

Problem

For a single vehicle that must visit each location once and return to its depot, the basic problem is the travelling-salesperson problem (TSP). The optimization version asks for the shortest tour. Its decision version—whether a tour of length at most `B` exists—is NP-complete. With multiple vehicles, capacities, and time windows, the problem becomes a richer vehicle-routing problem and remains computationally difficult.

Analysis

An exact algorithm that enumerates all tours has factorial growth, approximately `(n−1)!` tours for `n` locations when the starting depot is fixed. Even dynamic programming methods such as Held–Karp reduce the time to `Θ(n²2ⁿ)`, which is still exponential. Thus exact computation becomes impractical as the number of locations grows.

Approach

The company adopts a layered strategy:

1. Use clustering to divide customers geographically.

2. Construct an initial route using a greedy insertion heuristic.

3. Improve routes using local search, such as 2-opt, which repeatedly removes two edges and reconnects the segments if the total route becomes shorter.

4. Use an integer-programming solver for small daily instances.

5. Apply time limits and return the best feasible solution found for larger instances.

6. Monitor constraint violations, fuel estimates, delivery fairness, and customer service levels rather than distance alone.

Outcome

The resulting system does not guarantee a globally optimal route for every large instance, but it provides high-quality feasible routes within operational time limits. Exact optimization remains useful for small instances and for benchmarking heuristics.

Learning points

• A problem may be well specified yet computationally difficult.
• NP-hardness does not mean that useful solutions are impossible.
• Approximation and heuristic methods should be evaluated against explicit quality and time objectives.
• Operational constraints can matter more than an abstract distance objective.
• A claimed solution should be validated for feasibility, not only for its numerical score.

11. Limitations, Ethics, and Best Practices

11.1 Limitations of asymptotic analysis

Asymptotic notation hides constants and lower-order terms. An `O(n log n)` implementation may be slower than an `O(n²)` implementation for small `n`. It also usually abstracts away hardware, parallelism, memory hierarchy, input distributions, and implementation overhead.

Complexity classes describe asymptotic behavior, not exact runtime. Two algorithms with the same complexity may have very different practical performance. Empirical benchmarking, profiling, and workload-specific testing should complement theoretical analysis.

11.2 Ethical and governance considerations

Algorithmic decisions can affect access to credit, employment, healthcare, education, and public services. Efficiency must not be treated as the sole objective. Designers should consider:

• fairness and disparate impact;
• privacy and data minimization;
• transparency and explainability;
• robustness against adversarial or unusual inputs;
• accountability for automated decisions;
• accessibility and unequal access to computational resources.

A faster algorithm that systematically disadvantages a protected group is not an ethically successful solution. Requirements, evaluation metrics, and deployment controls should reflect social as well as technical risks.

11.3 Best practices

1. State the input model and constraints explicitly.

2. Separate correctness arguments from performance claims.

3. Report worst-case and, when justified, average-case behavior.

4. Define whether space complexity includes input storage.

5. Use reductions carefully and preserve their direction.

6. Test boundary cases, malformed inputs, and adversarial cases.

7. Benchmark representative workloads rather than relying only on synthetic examples.

8. Document approximation quality, timeout behavior, and failure modes.

9. Prefer reproducible experiments and version-controlled implementations.

10. Match algorithmic objectives to legal, ethical, and operational requirements.

Chapter Summary

Algorithms are finite, precise procedures that transform inputs into outputs. Pseudocode provides a language-independent way to express them, while correctness proofs use loop invariants, induction, and termination arguments. Time and space complexity describe resource use as a function of input size. Big-O gives an asymptotic upper bound, Big-Omega a lower bound, and Big-Theta a tight bound. Linear search, binary search, sorting algorithms, and recurrence relations illustrate how complexity is derived.

Divide and conquer, greedy design, dynamic programming, and backtracking are important algorithmic paradigms, each requiring particular structural conditions. Computational complexity classifies decision problems into categories such as P, NP, NP-hard, and NP-complete. Polynomial-time reductions are central to proving computational difficulty. In AI and industry, difficult problems such as routing and scheduling are commonly addressed through heuristics, approximation, restricted formulations, and hybrid exact methods. Sound algorithm engineering combines formal analysis with benchmarking, validation, ethical review, and awareness of practical constraints.

Key Terms

Algorithm: A finite, definite procedure for solving a specified problem.

Pseudocode: A language-independent representation of algorithmic logic.

Correctness: The property that an algorithm produces the required result for every valid input.

Loop invariant: A statement that remains true throughout loop execution.

Termination: The property that an algorithm eventually stops for every valid input.

Time complexity: The growth of computational work as input size increases.

Space complexity: The growth of memory requirements as input size increases.

Big-O: An asymptotic upper bound.

Big-Omega: An asymptotic lower bound.

Big-Theta: An asymptotically tight bound.

Recurrence: An equation defining the cost of a recursive algorithm in terms of smaller inputs.

Divide and conquer: A paradigm that divides, recursively solves, and combines subproblems.

Greedy algorithm: An algorithm that repeatedly makes a locally selected choice.

Dynamic programming: A method that stores solutions to overlapping subproblems.

Backtracking: Systematic search that abandons invalid partial solutions.

Tractable: Usually solvable in polynomial time.

P: The class of decision problems solvable in deterministic polynomial time.

NP: The class of decision problems whose proposed solutions can be verified in polynomial time.

NP-hard: At least as difficult as every problem in NP under polynomial-time reductions.

NP-complete: A problem that is both in NP and NP-hard.

Review Questions

Short Answer Questions

1. What properties distinguish an algorithm from an informal set of instructions?

2. Define a loop invariant and name the three stages of an invariant proof.

3. What is the difference between Big-O and Big-Theta notation?

4. Why does binary search require sorted data?

5. What is meant by saying that a decision problem belongs to NP?

Long Answer Questions

1. Explain how to prove total correctness using partial correctness and termination, illustrating the explanation with a simple loop.

2. Compare merge sort and quicksort in terms of design, best-case and worst-case complexity, auxiliary space, and practical use.

3. Explain the Master Theorem and apply it to the recurrence `T(n) = 2T(n/2) + Θ(n)`.

4. Compare greedy algorithms and dynamic programming, including the structural conditions that support each approach.

5. Explain P, NP, NP-hard, and NP-complete, and discuss why the P versus NP question matters in computing.

Analytical / Application Questions

1. Design pseudocode for an algorithm that determines whether an array contains duplicate values. Give two implementations with different time-space trade-offs and analyze both.

2. A delivery system must select routes for 100 locations under time-window constraints. Explain why an exact method may be impractical and propose a justified hybrid solution.

3. Consider an algorithm with recurrence `T(n) = T(n−1) + Θ(n)`. Derive its asymptotic complexity and identify a common algorithmic situation that can produce this recurrence.

Multiple Choice Questions with Answers

Question 1

Which statement best describes Big-Theta notation?

A. It gives only an upper bound on growth.

B. It gives only a lower bound on growth.

C. It gives an asymptotically tight bound.

D. It gives the exact runtime on every machine.

Correct Answer: C. It gives an asymptotically tight bound.

Question 2

What is the worst-case time complexity of binary search on a sorted array of n elements?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 3

Which component is required in a loop-invariant proof?

A. Randomized testing

B. Initialization, maintenance, and termination

C. A polynomial-time reduction

D. A recursion tree only

Correct Answer: B. Initialization, maintenance, and termination

Question 4

What is the standard worst-case time complexity of merge sort?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 5

Which condition is essential for binary search?

A. The array must contain distinct values.

B. The array must be sorted according to the comparison used.

C. The array must have an even length.

D. The array must be stored as a linked list.

Correct Answer: B. The array must be sorted according to the comparison used.

Question 6

Which property is characteristic of dynamic programming?

A. It always makes the locally cheapest choice.

B. It requires all problems to be undecidable.

C. It uses overlapping subproblems and stored subproblem solutions.

D. It never uses recursion.

Correct Answer: C. It uses overlapping subproblems and stored subproblem solutions.

Question 7

A decision problem is in NP when which condition holds?

A. Every instance has a unique solution.

B. A proposed yes-solution can be verified in polynomial time.

C. It has an exponential-time algorithm.

D. It is necessarily NP-complete.

Correct Answer: B. A proposed yes-solution can be verified in polynomial time.

Question 8

Which statement about NP-complete problems is correct?

A. They are all known to require exponential time.

B. They are both in NP and NP-hard.

C. They are all optimization problems rather than decision problems.

D. They cannot be solved for any finite input.

Correct Answer: B. They are both in NP and NP-hard.

Question 9

What is the asymptotic complexity of T(n) = T(n−1) + Θ(n)?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: D. Θ(n²)

Question 10

Why are heuristics commonly used for large routing problems?

A. Routing problems always have incorrect specifications.

B. Many routing formulations are computationally difficult, making exact optimization costly at scale.

C. Heuristics guarantee a globally optimal solution.

D. Heuristics eliminate the need to check feasibility.

Correct Answer: B. Many routing formulations are computationally difficult, making exact optimization costly at scale.