Foundations of Algorithmic Analysis

Introduction

Algorithmic analysis studies the resources required by an algorithm and the conditions under which its output is correct. For postgraduate work in artificial intelligence and machine learning, this analysis is not an optional theoretical exercise. The choice between an exact algorithm, an approximation method, a randomized procedure, or a heuristic often determines whether an AI system can be deployed at all.

A model-training pipeline may process millions of examples, a graph-learning system may operate on billions of edges, and an inference service may have only a few milliseconds to respond. In each case, an algorithm must be evaluated not only by whether it produces the desired result, but also by how its time and memory requirements grow as the input grows.

This chapter develops the foundations needed to analyse algorithms rigorously. It introduces computational models, asymptotic notation, recurrences, correctness proofs, loop invariants, lower bounds, tractability, and time–space trade-offs. The emphasis is on transferable reasoning rather than memorising isolated complexity classes.

Learning Objectives

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

1. Define an input-size measure and select an appropriate computational model.
2. Use Big-O, Big-Ω, and Big-Θ notation correctly.
3. Analyse iterative and recursive algorithms, including recurrence relations.
4. Prove algorithm correctness using induction, loop invariants, and exchange arguments.
5. Distinguish upper bounds, lower bounds, and tight bounds.
6. Explain tractability, intractability, and the role of approximation and randomisation.
7. Evaluate time–space trade-offs in AI and ML systems.
8. Critically interpret complexity claims in practical engineering settings.

1. Algorithms, Inputs, and Computational Resources

An algorithm is a finite, precisely specified procedure that maps valid inputs to outputs and eventually terminates. Algorithmic analysis requires three choices: the input representation, the size of the input, and the computational resources being measured.

1.1 Input size is problem-dependent

Input size is not always the number of objects. For an array of n values, n is usually an appropriate measure. For an integer N represented in binary, however, the input length is approximately log₂N bits, not N. An algorithm taking time proportional to N is therefore exponential in the length of the encoded input.

For a graph G = (V, E), common parameters include:

• n = |V|, the number of vertices;
• m = |E|, the number of edges;
• b, the number of bits used to represent numerical weights;
• n + m, often used for sparse graph algorithms.

For a machine-learning data set, useful parameters might include the number of observations, feature dimension, number of non-zero entries, model parameters, sequence length, or vocabulary size. The most informative analysis often uses several parameters rather than collapsing everything into one symbol.

1.2 Computational models

A computational model specifies which operations are considered elementary and their assumed costs. The unit-cost RAM model treats arithmetic on a machine word, memory access, comparison, and assignment as constant-time operations. This model is useful for arrays, pointers, and standard data structures.

The bit-complexity model counts operations on individual bits. It is essential when integers can grow large, because adding two b-bit integers is not necessarily constant time. Similarly, the word-RAM model reflects realistic fixed-width computer words and is useful for systems analysis.

For parallel algorithms, work and span are distinct. Work is the total number of primitive operations, while span is the length of the longest dependency chain. A computation may have large work but small span and therefore be suitable for parallel hardware.

Complexity results must therefore state their model. A claim such as “sorting takes linear time” is incomplete unless it specifies assumptions, such as bounded integer keys and a word-RAM model.

2. Asymptotic Analysis

Asymptotic notation describes growth as the input size tends toward infinity. It suppresses machine-dependent constants and lower-order terms, allowing algorithms to be compared at scale.

2.1 Big-O: asymptotic upper bound

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

Here, c and n₀ are constants independent of n. Big-O is an upper bound, not necessarily a tight description. For example, n is O(n²), although Θ(n) is more informative.

2.2 Big-Ω: asymptotic lower bound

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

This states that f grows at least as fast as g, up to a constant factor.

2.3 Big-Θ: tight asymptotic bound

A function f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). Equivalently, there exist positive constants c₁, c₂, and n₀ such that:

For example, 3n² + 7n + 4 is Θ(n²), because the quadratic term dominates asymptotically.

2.4 Common growth rates

From slower to faster growth, a typical ordering is:

The ordering is asymptotic. For small inputs, constants and implementation details can make a theoretically slower algorithm faster in practice.

2.5 Rules for analysing code

Sequential sections add their costs. If one section costs Θ(n) and another costs Θ(n²), the total is Θ(n²). Nested loops usually multiply iteration counts, although dependencies must be examined carefully.

For example:

for i = 1 to n:
    for j = 1 to i:
        perform constant-time operation

The number of operations is:

A loop that repeatedly halves its input has logarithmic complexity. If the value becomes n, n/2, n/4, and so on, after k iterations it is n/2ᵏ. The loop stops when n/2ᵏ ≤ 1, which gives k ≥ log₂n.

Best-case, worst-case, and average-case complexity must be distinguished. Worst-case analysis provides a guarantee for every input of a given size. Average-case analysis requires a probability distribution over inputs. Without such a distribution, “average case” is not mathematically defined.

3. Correctness and Proof Techniques

Efficiency is meaningful only for an algorithm that is correct. Correctness has two components: partial correctness, which says that a terminating algorithm returns a valid result, and termination, which says that the algorithm eventually stops. Together they establish total correctness.

3.1 Preconditions and postconditions

A precondition states what must be true before execution. A postcondition states what the algorithm guarantees after execution. For binary search, a typical precondition is that the input array is sorted in nondecreasing order. The postcondition is that the algorithm returns an index containing the target if one exists, and reports failure otherwise.

3.2 Mathematical induction

Induction is particularly useful for recursive algorithms and statements parameterised by n. A proof has a base case and an inductive step. In strong induction, the inductive step may assume the claim for all smaller values, which is natural for divide-and-conquer recurrences.

3.3 Loop invariants

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

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 stops, the invariant and the stopping condition imply the postcondition.

#### Example: insertion sort

Insertion sort maintains the invariant that the subarray preceding the current index is sorted and contains exactly the elements originally located there. During an iteration, the current element is shifted left until it reaches its correct position. The invariant is preserved. When all elements have been processed, the entire array is sorted.

Its worst-case running time is Θ(n²), because for a reverse-sorted array the ith insertion may shift Θ(i) elements. Its best-case time is Θ(n), because a sorted array requires only one comparison per element, subject to the implementation.

3.4 Variant functions and termination

To prove termination, identify a nonnegative quantity that decreases on every iteration and cannot decrease indefinitely. For a loop processing an array from left to right, the number of unprocessed elements is a natural variant. For Euclid’s algorithm, the positive remainder decreases strictly at each step, proving termination.

3.5 Exchange arguments

Greedy algorithms are often proved correct through an exchange argument. The proof shows that an optimal solution can be transformed into one containing the greedy choice without making it worse. Repeating this exchange establishes optimality.

This method is used for interval scheduling: selecting the compatible interval with the earliest finishing time leaves the largest possible remaining time for future intervals. The argument does not imply that every greedy algorithm is correct; the required exchange property must be established.

4. Recurrence Relations and Divide-and-Conquer

A recurrence expresses the cost of a recursive algorithm in terms of costs on smaller inputs. A typical divide-and-conquer recurrence is:

where a is the number of subproblems, n/b is the size of each subproblem, f(n) is the nonrecursive work, and b > 1. A base condition, such as T(1) = Θ(1), is also required.

4.1 Recursion-tree reasoning

Consider merge sort:

At each recursion level, the total merging work is Θ(n). The recursion depth is log₂n, so the total cost is:

The recursion also uses Θ(n) auxiliary space for merging, apart from the call stack.

4.2 The Master Theorem

For recurrences of the form T(n) = aT(n/b) + f(n), compare f(n) with n^(log_b a). Let p = log_b a.

• If f(n) = O(n^(p−ε)) for some ε > 0, then T(n) = Θ(n^p).
• If f(n) = Θ(n^p log^k n) for k ≥ 0, then T(n) = Θ(n^p log^(k+1)n).
• If f(n) = Ω(n^(p+ε)) for some ε > 0 and a regularity condition holds, then T(n) = Θ(f(n)).

The theorem does not apply automatically to every recurrence. Unequal subproblem sizes, floors, ceilings, unusual additive terms, or failure of the regularity condition may require substitution, recursion trees, or other methods.

For binary search, T(n) = T(n/2) + Θ(1), giving Θ(log n). For naïve recursive Fibonacci, T(n) = T(n−1) + T(n−2) + Θ(1), which is exponential; the Master Theorem does not apply because the subproblem sizes are not fixed fractions of n.

4.3 Substitution method

The substitution method proves a proposed bound by induction. To show T(n) = O(n log n), assume the claim holds for smaller inputs, substitute those bounds into the recurrence, and select constants large enough to absorb lower-order terms. This method is more flexible than the Master Theorem but requires careful algebra.

5. Lower Bounds and Optimality

An upper bound describes an algorithm; a lower bound describes the difficulty of a problem or model. A problem lower bound applies to every algorithm in a specified class, whereas an algorithmic lower bound applies to one particular algorithm.

5.1 Comparison sorting lower bound

Any comparison-based sorting algorithm can be represented by a decision tree. Sorting n distinct elements requires distinguishing among n! possible orderings. A binary decision tree of height h has at most 2^h leaves, so:

Therefore:

The last relationship follows from standard bounds on n!, such as log(n!) = Θ(n log n). Consequently, no comparison sort can have worst-case time o(n log n). Merge sort and heapsort achieve O(n log n), so they are asymptotically optimal in the comparison model.

This lower bound does not prohibit counting sort or radix sort, because those algorithms exploit information about keys beyond pairwise comparisons.

5.2 Decision-tree and adversary reasoning

Decision-tree arguments count the information that an algorithm must obtain. Adversary arguments imagine an opponent answering queries consistently while delaying the information needed to decide the output. Both methods clarify why a fast solution may be impossible under particular assumptions.

5.3 Complexity classes

P is the class of decision problems solvable in polynomial time by a deterministic algorithm. NP is the class of decision problems for which a proposed solution can be verified in polynomial time. NP-hard problems are at least as difficult as every problem in NP under an appropriate reduction; NP-complete problems are both in NP and NP-hard.

The famous P versus NP question remains unresolved. It is important not to infer that every NP problem is practically impossible or that every polynomial algorithm is practical. A polynomial such as n^100 may be unusable, while an exponential algorithm may be effective for small or highly structured inputs.

6. Tractability, Approximation, and Randomisation

Tractability is context-dependent. An algorithm is conventionally called tractable when its resource requirements are polynomial in the input length, but operational tractability also depends on constants, memory, hardware, latency limits, and input distributions.

When exact optimisation is expensive, several strategies are available:

• Approximation algorithms provide provable guarantees relative to an optimum.
• Heuristics seek good solutions without universal guarantees.
• Parameterised algorithms may be efficient when a secondary parameter is small.
• Randomised algorithms use random choices to obtain expected efficiency or simpler designs.
• Online algorithms make decisions without seeing future input.

For a minimisation problem, an approximation ratio of α ≥ 1 means the algorithm returns a solution with cost at most α times the optimum, under the stated assumptions. For maximisation, conventions differ, so the ratio must be defined explicitly.

Randomised analysis must distinguish expected running time, high-probability bounds, and worst-case running time. Randomness can reduce the likelihood of pathological inputs, but it does not automatically eliminate worst-case behaviour.

7. Time–Space Trade-offs

Time and space are separate resources. Reducing one may increase the other. The right choice depends on hardware cost, latency, throughput, data sensitivity, and operational constraints.

7.1 Memoisation and dynamic programming

Naïve recursive Fibonacci recomputes the same subproblems exponentially many times. Memoisation stores each result, reducing the time to Θ(n) and requiring Θ(n) additional space. Bottom-up dynamic programming has the same asymptotic time but may improve locality and avoid recursion overhead.

If only the two preceding Fibonacci values are needed, the space can be reduced to Θ(1). This is an example of state compression: retaining only information required by future computations.

7.2 Hashing and indexing

A hash table typically provides expected Θ(1) lookup under assumptions about the hash function and load factor, but worst-case lookup can be Θ(n). An index consumes memory and maintenance time but reduces query latency. In an ML feature store, precomputed embeddings or nearest-neighbour indexes similarly exchange storage and update cost for fast inference.

7.3 Caching and preprocessing

Preprocessing may cost Θ(n) or more and require additional storage, but repeated queries can then be answered quickly. The correct decision depends on the number of queries q. If preprocessing costs P and each unprocessed query costs U while each indexed query costs I, indexing is attractive when:

This inequality is a simplified decision rule; real systems must also include update, invalidation, and memory costs.

7.4 External memory and streaming

When data exceed RAM, block transfers between storage and memory dominate CPU operations. Streaming algorithms use limited memory and process data sequentially, often producing approximate summaries. Such methods are valuable for high-volume telemetry, clickstreams, and online learning, but they may sacrifice exactness or support for arbitrary queries.

8. Algorithmic Analysis in AI and Machine Learning

Complexity analysis appears throughout AI:

• Matrix multiplication affects neural-network training and inference.
• Graph traversal affects recommendation, routing, and knowledge graphs.
• Nearest-neighbour search affects retrieval-augmented generation and similarity systems.
• Dynamic programming appears in sequence alignment, decoding, and structured prediction.
• Search complexity affects planning, game playing, and combinatorial optimisation.

A training algorithm may be polynomial yet operationally expensive because the dimension, number of examples, or number of iterations is large. Conversely, sparsity can reduce practical cost. If an adjacency matrix has n² possible entries but only m nonzero edges, a sparse representation can reduce storage from Θ(n²) to Θ(n + m).

Complexity analysis also supports responsible AI. Resource-intensive models have environmental and financial costs. A technically accurate evaluation should report not only predictive accuracy but also training time, inference latency, memory use, hardware assumptions, batch size, and scaling behaviour. Approximation and compression can improve accessibility, but they must be evaluated for accuracy degradation and subgroup effects.

9. Illustrative Case: Choosing a Similarity-Search Strategy

Background

Consider a fictional online learning platform that recommends courses using vector embeddings. Each learner and course is represented by a d-dimensional vector. The service must return the k most similar courses from a catalogue of N items within a strict latency budget.

Problem

An exact scan computes similarity between the query and every catalogue vector. Under the unit-cost arithmetic model, this costs Θ(Nd) time per query and Θ(Nd) storage for the vectors. As N grows, latency becomes unacceptable.

Analysis

The engineering team considers three approaches:

1. Exact linear scan: simple and accurate, but Θ(Nd) time.
2. Precomputed index: additional construction and memory costs, but substantially fewer candidates examined per query.
3. Approximate nearest-neighbour search: lower expected query cost, with a tunable recall–latency trade-off.

The team measures recall@k, p95 latency, memory consumption, update time, and cost per million queries. Average latency alone is rejected because tail latency determines user experience.

Approach and solution

A two-stage design is selected. An approximate index retrieves a candidate set of size r, where r is much smaller than N. Exact similarities are then computed on those candidates, costing approximately Θ(rd) for reranking. The index is periodically rebuilt, while newly added courses are held in a small auxiliary structure.

The design is governed by explicit assumptions: the embedding distribution is reasonably stable, index updates are acceptable at the chosen frequency, and a small loss in recall is permissible. Monitoring detects distribution drift and changes in recall.

Outcome

The system meets its latency target while retaining a high proportion of the exact top-k results. The result is not “the fastest algorithm” in the abstract; it is the best choice under a stated objective involving latency, recall, memory, update frequency, and cost.

Learning points

1. Complexity must be connected to operational metrics.
2. Approximation is useful only when its error is measured.
3. Indexing converts repeated computation into preprocessing and storage.
4. Worst-case, expected, and tail behaviour should not be conflated.
5. AI systems require both algorithmic and governance monitoring.

10. Best Practices and Limitations

A rigorous analysis should:

• define input parameters and representation;
• state the computational model;
• separate correctness from efficiency;
• distinguish worst-case, average-case, and expected bounds;
• report both time and space;
• identify hidden assumptions, such as constant-time arithmetic;
• use tight bounds where justified rather than loose Big-O claims;
• test theoretical predictions against representative workloads;
• account for parallelism, caching, I/O, and hardware effects;
• document approximation error and randomisation assumptions.

Asymptotic analysis has limitations. It ignores constants and may be misleading for small inputs. It may not model cache locality, vectorisation, communication, energy, or accelerator utilisation. A theoretical complexity result is therefore a foundation for experimentation, not a substitute for measurement.

Ethically, algorithm designers should also consider whether efficiency improvements enable harmful surveillance, opaque decision-making, or inequitable access. Reducing computational cost is beneficial only when the system’s purpose, data practices, and impacts are acceptable.

Chapter Summary

Algorithmic analysis explains how algorithms behave as inputs scale. A sound analysis begins by defining input size and a computational model. Big-O gives an asymptotic upper bound, Big-Ω a lower bound, and Big-Θ a tight bound. Correctness requires both a valid result and termination; loop invariants, induction, variant functions, and exchange arguments provide reusable proof techniques.

Recurrence relations model recursive algorithms, with recursion trees, substitution, and the Master Theorem providing complementary solution methods. Lower-bound arguments, including decision trees, establish limits on what algorithm classes can achieve. Tractability depends on polynomial growth as well as practical constants, memory, hardware, and workload structure.

Time–space trade-offs appear in memoisation, indexing, caching, preprocessing, and streaming. In AI and ML, complexity analysis must be connected to latency, throughput, recall, energy, memory, and governance. The most useful algorithmic decision is therefore not merely the one with the best asymptotic notation, but the one whose assumptions and trade-offs fit the real application.

Key Terms

Asymptotic notation: Mathematical notation describing growth rates as input size becomes large.

Big-O: An asymptotic upper bound.

Big-Ω: An asymptotic lower bound.

Big-Θ: A tight asymptotic bound.

Computational model: A formalisation of available operations and their costs.

Input size: A measure of the amount of information supplied to an algorithm.

Loop invariant: A property preserved throughout loop execution.

Partial correctness: The guarantee that a terminating algorithm produces a valid result.

Total correctness: Partial correctness together with termination.

Recurrence relation: An equation describing a recursive algorithm’s cost using smaller inputs.

Divide-and-conquer: A method that decomposes a problem into smaller subproblems, solves them, and combines results.

Lower bound: A proof that no algorithm in a specified model can use fewer resources than a stated asymptotic amount.

Decision tree: A tree representing the sequence of decisions or comparisons made by an algorithm.

Tractable problem: A problem considered solvable within acceptable resource growth, conventionally polynomial time.

Approximation algorithm: An algorithm providing a solution with a stated quality guarantee.

Randomised algorithm: An algorithm whose behaviour depends partly on random choices.

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

Parameterised complexity: Analysis based on input size and one or more additional structural parameters.

Time–space trade-off: The exchange between computation time and memory use.

Tail latency: A high-percentile response time, such as p95 or p99 latency.

Review Questions

Short Answer Questions

1. Why must an algorithmic analysis specify the computational model?
2. State the definitions of Big-O and Big-Θ notation.
3. What are the three components of a loop-invariant proof?
4. Why does comparison-based sorting have an Ω(n log n) lower bound?
5. Give one example of a time–space trade-off in machine learning.

Long Answer Questions

1. Explain how input representation affects complexity, using binary-encoded integers as an example.
2. Compare recursion-tree analysis, substitution, and the Master Theorem for solving recurrences.
3. Explain the difference between partial correctness and total correctness, and illustrate both with a searching algorithm.
4. Discuss tractability, NP-hardness, approximation, and heuristics in the context of AI optimisation.
5. Analyse the benefits and limitations of asymptotic complexity for real production systems.

Analytical / Application Questions

1. An algorithm performs a linear preprocessing step and then answers q queries in constant time rather than linear time. Derive the inequality under which preprocessing is beneficial, and discuss assumptions omitted by the simplified model.
2. A graph has n vertices and m edges. Compare the storage and traversal implications of an adjacency matrix and a sparse adjacency-list representation. State when each representation is preferable.
3. Design a complexity-evaluation plan for an approximate nearest-neighbour service. Identify input parameters, correctness or quality metrics, time and space measures, and monitoring requirements.

Multiple Choice Questions with Answers

Question 1

Which statement best describes f(n) = Θ(g(n))?

A. f(n) is bounded above by g(n) only

B. f(n) is bounded below by g(n) only

C. f(n) is both O(g(n)) and Ω(g(n))

D. f(n) equals g(n) for every n

Correct Answer: C. f(n) is both O(g(n)) and Ω(g(n))

Question 2

What is the tight asymptotic complexity of the loop that executes i operations for each i from 1 through n?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: D. Θ(n²)

Question 3

Which condition is required in a loop-invariant proof?

A. The invariant must be false at initialization

B. The invariant must be preserved during every iteration

C. The loop must contain recursion

D. The algorithm must use constant space

Correct Answer: B. The invariant must be preserved during every iteration

Question 4

What is the recurrence for binary search under the usual comparison model?

A. T(n) = 2T(n/2) + Θ(n)

B. T(n) = T(n − 1) + Θ(1)

C. T(n) = T(n/2) + Θ(1)

D. T(n) = nT(n − 1) + Θ(1)

Correct Answer: C. T(n) = T(n/2) + Θ(1)

Question 5

Why does comparison sorting have an Ω(n log n) lower bound?

A. Every input contains exactly n log n comparisons

B. A decision tree must distinguish among n! possible orderings

C. All sorting algorithms use nested loops

D. The output requires n² memory

Correct Answer: B. A decision tree must distinguish among n! possible orderings

Question 6

Which technique reduces repeated computation by storing results of solved subproblems?

A. Memoisation

B. Random sampling

C. Exchange argument

D. Adversary analysis

Correct Answer: A. Memoisation

Question 7

Which statement about Big-O notation is correct?

A. It always denotes a tight bound

B. It describes an asymptotic upper bound

C. It applies only to recursive algorithms

D. It ignores the input representation in every model

Correct Answer: B. It describes an asymptotic upper bound

Question 8

If a preprocessing cost is P, indexed query cost is I, and unindexed query cost is U, when is indexing beneficial for q queries in the simplified model?

A. P + qI < qU

B. P + qU < qI

C. qP + I < U

D. P = I = U

Correct Answer: A. P + qI < qU

Question 9

Which statement correctly distinguishes work and span in parallel computation?

A. Work is the longest dependency chain, while span is total operations

B. Work and span are always equal

C. Work is total operations, while span is the longest dependency chain

D. Span measures memory and work measures latency only

Correct Answer: C. Work is total operations, while span is the longest dependency chain

Question 10

What is the main purpose of an approximation guarantee?

A. To prove that the algorithm always finds an exact optimum

B. To specify the quality of a returned solution relative to an optimum

C. To eliminate all memory use

D. To convert every exponential problem into a constant-time problem

Correct Answer: B. To specify the quality of a returned solution relative to an optimum