Algorithm Analysis and Correctness

Introduction

A program can produce the correct output and still be unsuitable for practical use. It may consume excessive time, require more memory than a device provides, or perform poorly when the input grows. Algorithm analysis provides a systematic way to predict these costs before implementation or deployment. Correctness reasoning addresses a complementary question: does the algorithm always produce the required result under its stated conditions?

This chapter develops the foundations needed to analyse algorithms written in Java and Python. It introduces asymptotic notation, common complexity classes, performance cases, amortized analysis, empirical measurement, and formal techniques for establishing correctness. The emphasis is on practical reasoning suitable for selecting algorithms and writing reliable software.

Learning Objectives

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

• explain time complexity, space complexity, and input size;
• use Big-O, Big-Theta, and Big-Omega notation correctly;
• identify best-case, average-case, and worst-case behaviour;
• distinguish amortized analysis from average-case analysis;
• measure algorithm performance empirically in Java and Python;
• state preconditions, postconditions, and loop invariants;
• apply induction, contradiction, and invariant-based proofs;
• evaluate the correctness and efficiency of practical algorithms.

1. What Algorithm Analysis Measures

An algorithm is a finite, precisely defined sequence of operations that transforms input into output. Analysis studies resources consumed as a function of input size. The most common resources are running time and memory.

Input size

Input size is represented by a variable such as n. Its meaning depends on the problem. For sorting, n is normally the number of elements. For a graph, the relevant parameters may be the number of vertices V and edges E. For integer arithmetic, the number of bits may be more meaningful than the numerical value itself.

A sound analysis defines its size measure explicitly. Saying that an algorithm is “linear” is incomplete unless the reader knows what is growing linearly.

Time complexity

Time complexity describes how the number of elementary operations grows with input size. It is not necessarily the elapsed time in seconds. Actual time depends on processor speed, language implementation, compiler optimisation, memory hierarchy, operating-system activity, and input data.

For example, a loop that examines every element in a list performs approximately n examinations and has linear time complexity. A nested pair of loops that examines every ordered pair may perform approximately n² operations and has quadratic time complexity.

Space complexity

Space complexity describes additional memory required by an algorithm as input size grows. It is useful to distinguish:

• Input space: memory occupied by the input itself.
• Auxiliary space: additional memory used by the algorithm.
• Total space: input space plus auxiliary space.

An in-place algorithm usually uses O(1) auxiliary space, although the precise definition can vary. A recursive algorithm may have small explicit data structures but still require O(n) call-stack space.

2. Asymptotic Notation

Asymptotic notation describes growth while ignoring constant factors and lower-order terms. This makes it useful for comparing algorithms across machines and implementation languages.

Big-O: asymptotic upper bound

A function f(n) is O(g(n)) if there exist constants c > 0 and n₀ > 0 such that:

Here, f(n) is the actual cost and g(n) is a comparison function. Big-O states that f(n) grows no faster than a constant multiple of g(n) beyond a sufficiently large input size.

Big-O is commonly used as an upper-bound statement, especially for worst-case complexity. However, it is mathematically possible for a function to belong to many Big-O classes. For example, n is also O(n²). Therefore, the tightest useful bound should normally be reported.

Big-Omega: asymptotic lower bound

A function f(n) is Ω(g(n)) if there exist constants c > 0 and n₀ > 0 such that:

This states that the cost grows at least as quickly as g(n) up to a constant factor.

Big-Theta: tight asymptotic bound

A function f(n) is Θ(g(n)) if there exist positive constants c₁, c₂, and n₀ such that:

Big-Theta gives both an asymptotic upper and lower bound. If an algorithm always scans all n elements, its running time is Θ(n), not merely [[MATH:O(n)].

Simplifying expressions

When analysing growth:

1. discard constant factors;
2. retain the fastest-growing term;
3. state the relevant input parameter.

For example:

The expression is quadratic because the n² term eventually dominates the linear and constant terms.

3. Common Complexity Classes

The logarithm base is usually omitted in asymptotic analysis because logarithms with different constant bases differ only by a constant factor. In implementation, however, the base can affect actual performance.

Sequential and nested operations

If two independent sections take Θ(n) and Θ(n²), their total is Θ(n²). For nested loops, multiply the iteration counts when the bounds are independent. Consider:

for i in range(n):
    for j in range(n):
        process(i, j)

The body executes n × n = n² times, so the time complexity is Θ(n²). If the inner loop runs from 0 to i, the total is:

Logarithmic loops

A loop that repeatedly doubles a variable has logarithmic iterations:

k = 1
while k < n:
    k *= 2

After t iterations, k = 2^t. The loop stops when 2^t ≥ n, so t ≥ log₂ n. Its complexity is Θ(log n).

4. Best, Average, Worst, and Amortized Performance

Complexity may depend on the particular input, not only its size.

Best-case analysis

Best-case complexity is the minimum cost among inputs of size n. For linear search, finding the target at the first position gives best-case Θ(1). Best-case results are useful but can be misleading if favourable inputs are unusual.

Worst-case analysis

Worst-case complexity is the maximum cost among inputs of size n. Linear search has worst-case Θ(n) when the target is absent or at the final position. Worst-case guarantees are important in safety-critical systems, service-level agreements, and applications vulnerable to adversarial inputs.

Average-case analysis

Average-case analysis calculates expected cost under a specified probability distribution over inputs. The distribution must be stated; “average” has no meaning without assumptions.

If a successful linear search is equally likely to find the target at any of the n positions, the expected number of comparisons is:

If unsuccessful searches are also possible, their probability must be included in the expectation.

Amortized analysis

Amortized analysis studies the average cost per operation over a sequence, without requiring a probability distribution. A particular operation may be expensive, but the average over the entire sequence is bounded.

A dynamic array illustrates this idea. Most append operations take constant time. When the array is full, resizing and copying may take Θ(n) time. If capacity is doubled whenever it fills, a sequence of n appends performs fewer than approximately 2n element copies. Thus the total cost is Θ(n), and the amortized cost per append is Θ(1).

This conclusion does not mean every append is constant time. It means the total cost of any sufficiently long sequence is linear in the number of appends.

5. Complexity in Java and Python

The abstract algorithm and the language implementation should be analysed separately. Python list indexing is typically constant time, while inserting at the beginning is linear because elements must be shifted. Java arrays also provide constant-time indexed access, while inserting into an array requires shifting elements. Java’s ArrayList and Python’s list are dynamic arrays with amortized constant-time append under their standard implementations.

Hash-table operations such as Python dictionary lookup and Java HashMap lookup are generally expected O(1) average time, but can be O(n) in the worst case. Their performance depends on hash quality, table resizing, collision handling, and implementation details.

Recursion introduces call-stack space. A recursive binary search uses O(log n) stack space if calls are not eliminated, even though its data structure usage may otherwise be constant. An iterative version can use O(1) auxiliary space.

6. Empirical Performance Evaluation

Asymptotic analysis should be complemented, not replaced, by measurement. A practical experiment should:

1. define the operation and input-size measure;
2. generate representative and adversarial inputs;
3. warm up the runtime when using a virtual machine or JIT compiler;
4. repeat trials and report suitable summaries;
5. control unrelated system activity where possible;
6. measure memory as well as time when memory is relevant.

In Python, timeit is preferable to a single call to time.time(). In Java, System.nanoTime() is more appropriate than wall-clock date functions for elapsed intervals, although serious benchmarking should use a framework such as JMH. Garbage collection, caching, compiler optimisation, and background processes can distort results.

A useful model for a measured runtime is:

where f(n) is the dominant growth function, a reflects implementation-dependent cost, and b represents fixed overhead. This is an empirical model, not a universal law.

Measurements should not be used to claim that one algorithm is always faster. A quadratic algorithm may outperform an O(n log n) algorithm for small inputs because of lower constants, simpler operations, or better cache behaviour.

7. Correctness: From Requirements to Proof

Efficiency is irrelevant if an algorithm returns incorrect results. A correctness argument begins by making the specification precise.

Preconditions and postconditions

A precondition is what must be true before execution. A postcondition is what the algorithm guarantees after successful termination.

For binary search on a sorted array:

• Precondition: the array is sorted in nondecreasing order, and the target and index boundaries are valid.
• Postcondition: if the algorithm returns index i, the element at i equals the target; if it returns “not found,” the target is absent from the array.

The algorithm is not required to produce a meaningful result when the precondition is violated. This distinction prevents vague claims of correctness.

Partial and total correctness

An algorithm is partially correct if, whenever it terminates and its preconditions hold, its postconditions hold. It is totally correct if it is partially correct and always terminates under the preconditions.

Termination must therefore be proved separately. A common method is a variant, a non-negative quantity that strictly decreases on every iteration. Since a strictly decreasing sequence of non-negative integers cannot continue forever, the loop terminates.

8. Loop Invariants

A loop invariant is a statement that remains true before and after every iteration. To prove correctness using an invariant, establish:

1. Initialization: the invariant is true before the first iteration;
2. Maintenance: if it is true before an iteration, it remains true afterward;
3. Termination: when the loop ends, the invariant combines with the exit condition to imply the postcondition.

Worked example: maximum value

Consider the following Python function:

def maximum(values):
    if not values:
        raise ValueError("empty sequence")
    current = values[0]
    for value in values[1:]:
        if value > current:
            current = value
    return current

Precondition: values is non-empty. Postcondition: the returned value is the maximum element of values.

Invariant: after processing the first k elements, current equals the maximum of those elements.

• Initialization: after assigning values[0], current is the maximum of the first element.
• Maintenance: the next value is compared with the current maximum. If it is larger, it becomes the new maximum; otherwise the existing maximum remains correct.
• Termination: all elements have been processed, so current is the maximum of the complete sequence.

The function is therefore correct under its precondition. Its time complexity is Θ(n), and its auxiliary space is Θ(1) excluding the slice created by values[1:]. If avoiding that slice is important, an index-based loop preserves Θ(1) auxiliary space.

9. Other Proof Techniques

Mathematical induction

Induction is useful for recursive algorithms and properties indexed by input size. A proof contains a base case and an inductive step. For example, correctness of merge sort can be argued by observing that arrays of size zero or one are sorted, and that merging two sorted halves produces a sorted whole.

Proof by contradiction

To prove that an algorithm cannot produce an invalid result, assume the contrary and derive an impossibility. This is common in greedy algorithms, where one assumes that a better solution exists and shows that an exchange preserves or improves the algorithm’s choice.

Exhaustive case analysis

Some algorithms have a small number of logically distinct cases. Correctness can be shown by proving each case separately, such as target found, target smaller than the midpoint, and target larger than the midpoint in binary search.

10. Detailed Application: Choosing a Search Strategy

Background

An online library maintains one million book identifiers. Users submit identifiers, and the system must report whether each identifier exists.

Problem

A developer proposes linear search through an unsorted Python list. Another proposes sorting the identifiers once and using binary search. A third proposes a hash-based set.

Analysis

For n identifiers and q queries:

• repeated linear search costs Θ(qn) in the worst case;
• sorting once costs Θ(n log n) and each binary search costs Θ(log n), giving Θ(n log n + q log n);
• constructing a hash set costs expected Θ(n) and queries cost expected Θ(1), giving expected Θ(n + q).

The hash set requires additional memory and depends on hashing assumptions. Sorted storage supports ordered traversal and predictable logarithmic worst-case search, while a hash set is generally preferable for pure membership testing.

Approach and solution

If the application only asks membership questions and memory is available, use a hash set. If identifiers must also be displayed in sorted order or predictable worst-case behaviour is required, maintain sorted storage and use binary search. For a small number of queries, avoiding preprocessing may make linear search acceptable.

Outcome

The appropriate choice depends on workload, memory, ordering requirements, and threat model. Complexity analysis prevents the decision from being based solely on the apparent simplicity of the code.

Learning points

• preprocessing can reduce repeated query cost;
• expected complexity depends on assumptions;
• space-time trade-offs are central to algorithm selection;
• requirements and correctness must be settled before optimisation.

11. Limitations, Professional Practice, and Ethics

Asymptotic notation hides constants, hardware effects, memory locality, parallelism, and input distributions. It should guide design, not replace testing. A complexity claim must state whether it is worst-case, expected, amortized, or empirical.

Correctness proofs also depend on the specification. A formally correct implementation of an unsafe or discriminatory requirement is not ethically acceptable. Engineers should validate input, protect personal data, avoid denial-of-service vulnerabilities, and consider adversarial inputs. Hash-table algorithms, parsers, and recursive procedures may require explicit resource limits to prevent resource exhaustion.

AI-assisted programming tools can suggest algorithms and tests, but generated code must be reviewed. Developers should verify invariants, boundary conditions, termination, complexity, licensing constraints, and security implications rather than treating generated output as proven correct.

Best Practices

• define input size and resource measures before analysing;
• report tight bounds when justified;
• distinguish expected, amortized, and worst-case claims;
• include preprocessing and output costs;
• state preconditions and postconditions;
• use invariants for loops and induction for recursion;
• test empty, singleton, boundary, duplicate, sorted, reverse-sorted, and adversarial inputs;
• benchmark representative workloads using suitable tools;
• document assumptions behind library-operation complexity;
• consider memory, security, maintainability, and correctness together.

Chapter Summary

Algorithm analysis predicts how time and memory grow as input size increases. Big-O gives an asymptotic upper bound, Big-Omega a lower bound, and Big-Theta a tight bound. Complexity may be described for best, average, or worst cases; amortized analysis instead bounds the cost of an operation sequence without requiring probabilities. Empirical measurement complements mathematical analysis but is affected by hardware and runtime conditions.

Correctness requires a precise specification. Preconditions describe required initial conditions, postconditions describe guarantees, and total correctness additionally requires termination. Loop invariants are proved through initialization, maintenance, and termination. Induction, contradiction, and case analysis provide additional proof methods. In professional software development, algorithm choice must balance complexity, memory, correctness, security, workload, and maintainability.

Key Terms

Input size: A measure of the amount of data processed by an algorithm.

Time complexity: Growth of operation cost as input size increases.

Space complexity: Growth of memory requirements as input size increases.

Auxiliary space: Additional memory used apart from the input.

Big-O: Asymptotic upper-bound notation.

Big-Omega: Asymptotic lower-bound notation.

Big-Theta: Asymptotically tight-bound notation.

Best case: Minimum cost over inputs of a given size.

Average case: Expected cost under a stated input distribution.

Worst case: Maximum cost over inputs of a given size.

Amortized analysis: Analysis of average cost over an operation sequence without probability assumptions.

Precondition: Requirement that must hold before execution.

Postcondition: Guarantee expected after successful execution.

Partial correctness: Correctness conditional on termination.

Total correctness: Partial correctness plus termination.

Loop invariant: A property preserved throughout loop execution.

Variant: A decreasing non-negative measure used to prove termination.

Empirical analysis: Performance evaluation through measurement.

Asymptotic growth: Behaviour of a function as input size becomes large.

Space-time trade-off: Exchange of memory usage for execution speed, or vice versa.

Review Questions

Short Answer Questions

1. What does Θ(n) mean?
2. Why is input size problem-dependent?
3. Distinguish worst-case analysis from amortized analysis.
4. What are the three stages of a loop-invariant proof?
5. Why can empirical measurements differ between Python and Java implementations?

Long Answer Questions

1. Explain Big-O, Big-Omega, and Big-Theta notation, including the meaning of constants and the threshold n₀.
2. Compare linear search, binary search, and hash-table lookup in terms of preprocessing, time, space, and assumptions.
3. Explain dynamic-array resizing and show why doubling capacity gives amortized constant-time append.
4. Describe how preconditions, postconditions, partial correctness, and total correctness work together.
5. Design a correctness argument and complexity analysis for a sorting algorithm of your choice.

Analytical / Application Questions

1. A program performs n operations, followed by a nested loop executing n² operations, followed by a logarithmic loop. Determine the overall tight asymptotic complexity and justify your answer.
2. An application receives one million membership queries against a collection that changes once per day. Choose between a sorted array with binary search and a hash set. Discuss time, memory, ordering, worst-case concerns, and update costs.
3. Construct a loop invariant and termination argument for an iterative algorithm that computes the sum of all elements in a non-empty array. State its precondition, postcondition, and time and space complexity.

Multiple Choice Questions with Answers

Question 1

Which notation expresses a tight asymptotic bound?

A. Big-O

B. Big-Omega

C. Big-Theta

D. Little-o

Correct Answer: C. Big-Theta

Question 2

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

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 3

A loop variable starts at 1 and doubles until it reaches n. What is its complexity?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 4

Which statement best describes amortized analysis?

A. It measures only the fastest input

B. It averages operation costs over a sequence without requiring probabilities

C. It always gives the worst cost of every operation

D. It measures elapsed time on one computer

Correct Answer: B. It averages operation costs over a sequence without requiring probabilities

Question 5

Which is required to prove total correctness?

A. Only a postcondition

B. Only termination

C. Partial correctness and termination

D. A benchmark with many inputs

Correct Answer: C. Partial correctness and termination

Question 6

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

A. The loop runs at least once

B. The invariant remains true after an iteration

C. The program uses constant space

D. The input is sorted before execution

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

Question 7

What is the expected number of comparisons when a successful linear search target is equally likely to be in any of n positions?

A. 1

B. log n

C. n/2

D. n²

Correct Answer: C. n/2

Question 8

Which data structure normally provides expected constant-time membership lookup?

A. Unsorted linked list

B. Balanced search tree

C. Hash set

D. Sorted array using linear search

Correct Answer: C. Hash set

Question 9

If an algorithm uses a recursive call stack of depth n, what auxiliary space may the stack require?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)

Question 10

Which statement about Big-O is correct?

A. It always gives an exact running time in seconds

B. It ignores the input size

C. It describes an asymptotic upper bound

D. It applies only to recursive algorithms

Correct Answer: C. It describes an asymptotic upper bound