Algorithm Analysis and Correctness

Introduction

A program is not valuable merely because it produces correct output for one input. A high-quality algorithm must be correct for every valid input and efficient enough for its intended environment. Algorithm analysis provides a systematic way to estimate resource usage, while correctness proofs establish that an algorithm satisfies its specification.

For full-stack developers, these ideas apply to database queries, API pagination, search, sorting, caching, authentication workflows, and client-side rendering. A solution that works on a ten-item test dataset may fail when deployed with millions of records. This chapter develops the mathematical and practical tools needed to reason about such behavior.

Learning Objectives

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

• distinguish correctness from efficiency;
• analyze best-case, average-case, and worst-case behavior;
• use O(g(n)), Ω(g(n)), and Θ(g(n)) correctly;
• derive and solve recurrence relations using substitution, recursion trees, and the Master Theorem;
• use loop invariants and mathematical induction to prove correctness;
• explain amortized analysis and apply it to dynamic arrays;
• design meaningful empirical benchmarks and interpret their limitations.

1. Correctness and Efficiency

An algorithm is partially correct if, whenever it terminates, its output satisfies the specification. It is totally correct if it is partially correct and always terminates for every valid input.

For example, a function that returns the position of a target in an array must specify what happens when the target is absent. A correct specification might state:

• if the target occurs, return an index containing it;
• otherwise, return −1;
• never access an invalid array position;
• terminate after examining a finite number of elements.

Efficiency is usually assessed using:

• time complexity: the number of elementary operations as a function of input size;
• space complexity: additional memory required as a function of input size.

Complexity analysis generally counts operations rather than seconds. Hardware, programming language, compiler optimization, and system load affect elapsed time, but the growth rate of an algorithm is more stable across environments.

2. Measuring Input Size and Cases

The symbol n commonly denotes input size, but the appropriate measure depends on the problem. For a string, n may be its number of characters; for a graph, input size may involve both vertices V and edges E; for matrix multiplication, dimensions may be more informative than one number.

For a fixed input size, different inputs can cause different running times:

• Best case: the least work required for any input of that size.
• Worst case: the greatest work required for any input of that size.
• Average case: expected work under an explicitly stated probability distribution over inputs.

Worst-case analysis gives a guarantee but may be pessimistic. Average-case analysis can be realistic, but only when the assumed distribution is justified. “Average case” does not mean the midpoint between best and worst cases.

Example: Linear Search

Consider searching for value x in an array of length n. A sequential search compares elements from left to right.

• Best case: 1 comparison, when the first element matches; complexity Θ(1):.
• Worst case: n comparisons, when the value is last or absent; complexity Θ(n):.
• If each position is equally likely and the value is guaranteed to occur, the expected comparisons are

where C is the number of comparisons. Thus the average case is Θ(n), although its constant factor is approximately one-half.

3. Asymptotic Notation

Asymptotic notation describes growth as n → ∞. It suppresses machine-dependent constants and lower-order terms.

Big-O: Upper Bound

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

This means g(n) is an asymptotic upper bound. It is correct to say that 3n + 7 = O(n), but also technically correct, though less informative, to say it is O(n²) because n grows no faster than n² for sufficiently large n.

Big-Omega: Lower Bound

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

It expresses an asymptotic lower bound.

Big-Theta: Tight Bound

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

Equivalently, f(n) is both O(g(n)) and Ω(g(n)).

Common Growth Rates

When analyzing sequential blocks, add their costs. For nested loops, examine how often the inner operation executes. A loop that doubles its counter each iteration performs Θ(log n) iterations, because after k iterations the counter is approximately 2^k, and solving 2^k ≥ n gives k ≥ log₂ n.

4. Recurrence Relations

Recursive algorithms are often described by recurrences. A recurrence defines running time in terms of smaller inputs. For example, binary search performs constant work and recursively searches one half:

Here c and d are positive constants, and the floor reflects integer input sizes.

Substitution Method

The substitution method has two stages: guess a bound and prove it by induction.

For binary search, guess T(n) = O(log n). Assume for smaller inputs that T(⌊n/2⌋) ≤ a log₂(⌊n/2⌋) + b. Then

Choosing a ≥ c makes the expression at most a log₂ n + b, after suitable treatment of the base case. Therefore T(n) = O(log n). A matching lower-bound argument gives Θ(log n).

The proof must check the base case and ensure that constants are chosen consistently; simply replacing a recurrence by a guessed answer is not a proof.

Recursion Trees

A recursion tree expands each recursive call by level. For merge sort,

At each level, the total nonrecursive work is cn. The tree has log₂ n internal levels, so the total internal work is cn log₂ n. The leaves contribute Θ(n). Hence

This method is especially useful for visualizing the contribution of different levels and for recurrences that do not fit a simple theorem.

Master Theorem

For a recurrence of the form

where a ≥ 1, b > 1, and f(n) is nonnegative asymptotically, compare f(n) with n^{log_b a}.

The regularity condition in Case 3 is important; the theorem must not be applied without checking its assumptions.

For merge sort, a = 2, b = 2, and f(n) = Θ(n). Since n^{log₂ 2} = n, this is Case 2 with k = 0, giving Θ(n log n).

The theorem does not directly apply to every recurrence. Unequal subproblem sizes, non-polynomial terms, or unusual recursive dependencies may require substitution, recursion trees, or other techniques.

5. Loop Invariants and Induction

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

1. Initialization: show the invariant is true before the first iteration.
2. Maintenance: show that if it is true before an iteration, it remains true afterward.
3. Termination: combine the invariant with the loop’s termination condition to prove the result.

Insertion Sort Invariant

Insertion sort processes an array from left to right. Before iteration j, the subarray A[0 … j−1] is sorted and contains exactly the elements originally in those positions.

• Initialization: before the first iteration, a one-element prefix is sorted.
• Maintenance: the algorithm shifts larger elements rightward and inserts A[j] into its proper position, so the enlarged prefix is sorted.
• Termination: when j = n, the entire array is sorted.

This proves functional correctness. Its worst-case time is Θ(n²) because the inner shifting operation can move approximately j elements on iteration j. Its best-case time is Θ(n) when the input is already sorted. It uses Θ(1) auxiliary space in its usual in-place implementation.

Mathematical Induction

Induction proves a statement over discrete values. To prove P(n):

• prove the base case, often P(1);
• assume P(k) for an arbitrary valid k;
• use that assumption to prove P(k+1).

Recurrence substitution proofs use strong induction when the result for n depends on several smaller input sizes rather than only n−1.

A related termination argument uses a variant: a nonnegative quantity that strictly decreases on every iteration or recursive call. For a loop moving an index toward n, the remaining distance n − i can serve as a variant.

6. Amortized Analysis

Amortized analysis studies the total cost of a sequence of operations. It does not use probability and does not claim that every individual operation is cheap. Instead, expensive operations are averaged over a worst-case sequence.

Dynamic Array Example

Suppose a dynamic array doubles its capacity when full. Most append operations cost constant time. An expansion may copy m existing elements and therefore cost Θ(m). However, after copying, at least m further positions become available.

For n appends, the total copying is bounded by

where 2^k is the largest capacity reached before or during the sequence. The total cost of n appends is therefore O(n), and the amortized cost per append is

The doubling policy also gives a geometric-series bound on unused capacity: immediately after expansion, the array may be approximately half empty, so space usage remains Θ(n), ignoring implementation metadata.

The accounting method can assign each append three units of credit: one pays for the immediate insertion and two are saved toward copying. The potential method formalizes saved work using a nonnegative potential function Φ; the amortized cost of operation i is

where cᵢ is actual cost and Dᵢ is the data structure state after operation i. If Φ(D₀) = 0 and potential never becomes negative, the sum of amortized costs bounds the total actual cost.

Amortized bounds are different from average-case bounds: amortized analysis considers operation sequences deterministically, whereas average-case analysis depends on a probability model.

7. Empirical Benchmarking

Asymptotic analysis should be complemented—not replaced—by measurement. A useful benchmark follows a controlled process:

1. define the performance question and metric;
2. implement equivalent algorithms carefully;
3. generate representative, worst-case, and edge-case inputs;
4. warm up the runtime when using a virtual machine or JIT compiler;
5. repeat trials and report median or distribution, not only one run;
6. control hardware, software version, background load, and compiler settings;
7. vary n over a meaningful range;
8. inspect results for scaling trends and outliers.

Wall-clock time is affected by I/O, memory hierarchy, garbage collection, operating-system scheduling, network latency, and data distribution. A benchmark should therefore report what was measured. For a web service, throughput, latency percentiles, memory, and error rate may be more meaningful than a single execution time.

Benchmarking can reveal constant-factor differences that asymptotic notation hides. For example, an O(n log n) algorithm may outperform another with the same complexity because it has better locality. Conversely, an O(n²) algorithm may be faster for very small inputs because of low overhead. Such observations do not invalidate asymptotic analysis; they identify the range in which constants and machine effects matter.

8. Applied Case: Selecting a Search Strategy for a Product Catalogue

Background

An illustrative online store maintains product identifiers and must answer frequent membership queries. The catalogue contains between 10,000 and 10 million identifiers.

Problem

The engineering team considers linear search, binary search on a sorted array, and hash-based lookup. It must balance query latency, update cost, memory, and predictable behavior.

Analysis

Linear search requires Θ(n) worst-case comparisons per query and is simple, but it scales poorly. Binary search requires sorted data and has Θ(log n) worst-case query time, while insertion into a contiguous sorted array can cost Θ(n). A hash table typically provides expected Θ(1) lookup under suitable hashing and load-factor assumptions, but worst-case lookup can be Θ(n) in an adversarial or highly colliding situation.

If the catalogue is mostly static and memory locality is important, a sorted array may be attractive. If updates and high-volume membership queries dominate, a hash table is usually more suitable. If predictable worst-case behavior is essential, the design should consider a balanced search tree, whose search and update operations are Θ(log n) when height is maintained logarithmically.

Approach and Outcome

The team benchmarks all candidates using absent identifiers, common identifiers, random identifiers, and update batches. It reports median and high-percentile latency separately. The final design uses a hash table for the primary service and periodically validates results against a sorted snapshot. This choice is not justified by “constant time” alone: the team also evaluates memory overhead, resizing behavior, collision handling, security, and update semantics.

Learning Points

• Complexity bounds describe scaling, not exact seconds.
• Average or expected bounds require assumptions.
• Data distribution and workload mix affect practical performance.
• Correctness includes behavior for missing identifiers and concurrent updates.
• Measurement should test realistic and adversarial cases.

9. Limitations, Professional Practice, and Contemporary Considerations

Asymptotic models often assume unit-cost arithmetic, uniform memory access, and negligible system overhead. These assumptions are imperfect. Large integers may require more than constant time, caches make memory access nonuniform, and distributed calls introduce network costs. A full-stack analysis should include serialization, database access, external APIs, and concurrency where relevant.

Correctness also extends beyond output values. Production algorithms should address input validation, privacy, authorization, failure handling, resource exhaustion, and denial-of-service risks. An algorithm with a theoretically strong average case may be unsafe if an attacker can construct worst-case inputs. Hash-table implementations, parsers, and regular-expression engines therefore require adversarial analysis.

AI-assisted code generation does not remove the need for proofs or tests. Generated code may contain incorrect loop bounds, hidden quadratic behavior, unsafe recursion, or unhandled edge cases. Developers should derive the specification, inspect invariants, test boundary cases, and benchmark independently. Automated tests provide evidence; a proof explains why the algorithm is correct for all inputs covered by its assumptions.

Best practice is to combine four forms of reasoning:

• formal specification and proof for correctness;
• asymptotic analysis for scalability;
• amortized or probabilistic analysis where appropriate;
• empirical measurement for implementation reality.

Chapter Summary

Algorithm analysis separates growth-rate reasoning from machine-specific timing. Best-case, average-case, and worst-case measures answer different questions and require clear assumptions. Big-O expresses an upper bound, Big-Omega a lower bound, and Big-Theta a tight asymptotic bound. Recurrences model recursive algorithms and can be solved using substitution, recursion trees, or the Master Theorem when its conditions hold.

Loop invariants, induction, and termination variants provide rigorous correctness arguments. Amortized analysis bounds the cost of operation sequences without relying on probability; dynamic-array expansion is a central example. Empirical benchmarking exposes constants, hardware effects, and workload behavior, but must be controlled and interpreted alongside theory. Professional algorithm selection considers correctness, scalability, memory, adversarial inputs, maintainability, and system-level costs.

Key Terms

Asymptotic notation: Mathematical description of growth as input size becomes large.

Big-O: An asymptotic upper bound.

Big-Omega: An asymptotic lower bound.

Big-Theta: A tight asymptotic bound.

Best case: Least work for inputs of a specified size.

Worst case: Greatest work for inputs of a specified size.

Average case: Expected work under a stated probability distribution.

Recurrence: Equation defining a recursive cost in terms of smaller costs.

Substitution method: Guess-and-prove technique for solving recurrences.

Recursion tree: Expansion of recursive calls by levels.

Master Theorem: Theorem for selected divide-and-conquer recurrences.

Loop invariant: Statement preserved across loop iterations.

Mathematical induction: Proof method using a base case and inductive step.

Termination variant: Nonnegative quantity that strictly decreases toward termination.

Amortized analysis: Analysis of total cost over an operation sequence.

Potential function: Stored-value function used in potential-based amortized analysis.

Benchmark: Controlled measurement of program performance.

Load factor: Ratio of stored entries to hash-table capacity.

Correctness: Satisfaction of an algorithm’s specification for all valid inputs.

Complexity: Resource growth as a function of input size.

Review Questions

Short Answer Questions

1. Distinguish total correctness from partial correctness.
2. Why is average-case analysis incomplete without a probability distribution?
3. State the three conditions used to prove a loop invariant.
4. Why can dynamic-array append have O(1) amortized cost despite occasional linear expansions?
5. What does the regularity condition do in Case 3 of the Master Theorem?

Long Answer Questions

1. Explain Big-O, Big-Omega, and Big-Theta, including their formal inequalities and an example of each.
2. Solve T(n)=2T(n/2)+Θ(n) using a recursion-tree argument.
3. Present a loop-invariant proof of insertion sort correctness.
4. Compare worst-case, average-case, and amortized analysis, emphasizing their assumptions.
5. Design a benchmark for comparing binary search and hash-table lookup in a production catalogue.

Analytical / Application Questions

1. A recursive algorithm satisfies T(n)=3T(n/2)+n. Use the Master Theorem to classify its asymptotic complexity and justify the applicable case.
2. A web endpoint scans all n user records and, for each record, performs a binary search in a sorted list of n permissions. Derive the overall time complexity and identify a design improvement.
3. An adversary can choose inputs for a hash table. Explain why expected Θ(1) lookup does not guarantee worst-case Θ(1) behavior, and recommend two mitigations.

Multiple Choice Questions with Answers

Question 1

Which notation represents a tight asymptotic bound?

A. O(g(n)) only

B. Ω(g(n)) only

C. Θ(g(n))

D. Little-o notation only

Correct Answer: C. Θ(g(n))

Question 2

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

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 3

In a loop-invariant proof, what does maintenance establish?

A. The loop has no input

B. The invariant remains true after an iteration

C. The algorithm uses constant space

D. The loop executes exactly once

Correct Answer: B. The invariant remains true after an iteration

Question 4

For T(n)=2T(n/2)+Θ(n), which Master Theorem result applies?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 5

Why is dynamic-array append typically Θ(1) amortized?

A. Every append copies no elements

B. Expensive expansions occur often enough to cancel savings

C. The total copying over a sequence is linear in the number of appends

D. The array has unlimited capacity

Correct Answer: C. The total copying over a sequence is linear in the number of appends

Question 6

Which statement about average-case analysis is correct?

A. It always equals the midpoint of best and worst cases

B. It requires an assumption about input probabilities

C. It is identical to amortized analysis

D. It ignores input size

Correct Answer: B. It requires an assumption about input probabilities

Question 7

A loop doubles its counter until it reaches n. How many iterations does it have asymptotically?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 8

Which condition is necessary for total correctness?

A. The algorithm must use recursion

B. The algorithm must terminate and satisfy its specification

C. The algorithm must have Θ(1) time

D. The algorithm must be randomized

Correct Answer: B. The algorithm must terminate and satisfy its specification

Question 9

What is the main purpose of a termination variant?

A. To show that a quantity decreases toward termination

B. To calculate average memory usage

C. To select a programming language

D. To establish a probability distribution

Correct Answer: A. To show that a quantity decreases toward termination

Question 10

Which benchmark practice most improves interpretability?

A. Run one trial under unknown system load

B. Use only the smallest input

C. Control conditions, repeat trials, and vary input size

D. Measure only source-code length

Correct Answer: C. Control conditions, repeat trials, and vary input size