Data Structures and Algorithms

Chapter 2
Algorithm and Complexity Analysis

Bachelors Program in AI & ML
Data Structures and Algorithms • Bachelor

Algorithm and Complexity Analysis

Introduction and Context

An algorithm is a finite, precise sequence of instructions for solving a problem or transforming input into output. In data structures and algorithms, correctness is necessary but not sufficient: an algorithm must also use acceptable computational resources. Complexity analysis provides a principled way to predict how execution time and memory requirements grow as input size increases.

This perspective is especially important in artificial intelligence and machine learning. Training, searching, sorting, graph traversal, nearest-neighbour retrieval, feature processing, and model inference may all involve very large datasets. An algorithm that performs well on one thousand records may become unusable on one billion records. Complexity analysis helps engineers compare alternatives before implementation, identify bottlenecks, and reason about scalability independently of a particular computer.

The central resources considered in this chapter are:

Time complexity: how the number of elementary operations grows with input size.
Space complexity: how additional memory requirements grow with input size.
Asymptotic analysis: description of growth for large inputs.
Case analysis: comparison of best, average, and worst inputs.
Amortized analysis: average cost over a sequence of operations, without relying on probability.
Lower bounds: limits on the performance any algorithm can achieve under a specified model.
Empirical benchmarking: measurement of actual performance on real systems.

Learning Objectives

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

1. Define input size and count elementary operations in an algorithm.

2. Use Big-O, Big-Ω, and Big-Θ notation correctly.

3. Analyze common loops, nested structures, recursion, and space requirements.

4. Formulate and solve basic recurrence relations.

5. Distinguish best-case, average-case, worst-case, and amortized complexity.

6. Explain lower bounds and recognize when an algorithm is asymptotically optimal.

7. Design meaningful empirical benchmarks and interpret their results.

8. Evaluate performance trade-offs relevant to software and AI/ML systems.

1. Measuring Algorithmic Efficiency

1.1 Input size and computational models

Complexity is meaningful only after the input size has been defined. For an array, the size is usually the number of elements, denoted by $n$. For a graph, one may need both the number of vertices $V$ and edges $E$. For a matrix, dimensions such as $m$ rows and $n$ columns are relevant. For a machine-learning dataset, input size might include the number of records, features, model parameters, or total nonzero values in a sparse representation.

A unit-cost model treats basic operations—such as comparisons, assignments, arithmetic operations, and array indexing—as taking constant time. This is an abstraction. On actual hardware, cache misses, memory allocation, integer size, vectorization, and parallelism affect execution time. Nevertheless, the model is valuable because it exposes growth trends.

An operation is considered constant time when its cost is bounded independently of the input size under the chosen model. Accessing an element by index in a conventional array is commonly modeled as $O(1)$. Multiplying arbitrary-precision integers is not necessarily $O(1)$ because the cost depends on the number of digits.

1.2 Growth rates

Suppose an algorithm performs

$$T(n)=3n^2+5n+7$$

basic operations. For large $n$, the quadratic term dominates. The constants and lower-order terms matter in practice, but asymptotic analysis focuses on growth. Thus, $T(n)$ is $Theta(n^2)$, and consequently it is also $O(n^2)$ and $Omega(n^2)$.

Common growth rates, from generally smaller to larger for sufficiently large $n, are:

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

The ordering is asymptotic; for small inputs, constants can reverse practical performance. A carefully optimized quadratic algorithm may outperform a poorly implemented $n\log n$ algorithm for modest input sizes.

2. Asymptotic Notation

2.1 Big-O: an asymptotic upper bound

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

$$0\le f(n)\le c g(n) \quad \text{for all } n\ge n_0.$$

Big-O states that $f$ grows no faster than a constant multiple of $g$ beyond a sufficiently large threshold. It is commonly used as an upper bound on running time, but it does not necessarily mean that the bound is tight.

For example, $5n+10$ is $O(n)$ and also $O(n^2)$. The statement $O(n)$ is more informative because it is tighter.

2.2 Big-Ω: an asymptotic lower bound

A function $f(n)$ is $\Omega(g(n))$ if there exist constants $c>0$ and $n_0$ such that

$$0\le c g(n)\le f(n) \quad \text{for all } n\ge n_0.$$

This indicates that $f$ grows at least as quickly as $g$, up to a constant factor.

2.3 Big-Θ: a tight asymptotic bound

A function $f(n)$ is $\Theta(g(n))$ if there exist positive constants $c_1,c_2$ and $n_0$ such that

$$0\le c_1g(n)\le f(n)\le c_2g(n) \quad \text{for all } n\ge n_0.$$

Big-Θ is the most precise of the three standard notations when both upper and lower bounds are known. Saying that an algorithm takes $\Theta(n\log n)$ time means its growth is bounded above and below by constant multiples of $n\log n$.

2.4 Simplification rules

The following rules are useful under ordinary asymptotic analysis:

Constant factors are ignored: $7n=\Theta(n)$.
Lower-order terms are ignored: $n^2+n=\Theta(n^2)$.
Sequential sections add: $\Theta(n)+\Theta(n^2)=\Theta(n^2)$.
Independent nested loops often multiply: a loop of $n$ iterations inside another loop of $n$ iterations is $\Theta(n^2)$.
Logarithm bases differ only by a constant factor: $\log_2 n=\Theta(\log_{10}n)$.

These rules assume that operations within the model have the stated costs and that the input representation is understood.

3. Analyzing Iterative Algorithms

Consider linear search through an array of $n$ elements. It compares the target with elements from left to right until it finds a match or reaches the end.

Best case: the target is first, requiring one comparison, so the time is $\Theta(1)$.
Worst case: the target is last or absent, requiring $n$ comparisons, so the time is $\Theta(n)$.
If the target is equally likely to occur at any position and is guaranteed to occur, the expected number of comparisons is $(n+1)/2$, which is $\Theta(n)$.

The average-case result depends on the probability model. If successful and unsuccessful searches have different probabilities, the expected cost changes. Therefore, “average case” must never be stated without specifying how inputs are distributed.

As an example of loop analysis, consider:

```text

for i = 1 to n:

for j = 1 to i:

perform constant-time operation

```

The operation executes

$$1+2+\cdots+n=\frac{n(n+1)}{2}$$

times. Therefore its time complexity is $\Theta(n^2)$.

Now consider a loop whose variable doubles:

```text

i = 1

while i < n:

perform constant-time operation

i = 2i

```

After $k$ iterations, $i=2^k$. The loop stops when $2^k\ge n$, so $k\ge \log_2 n$. The running time is $\Theta(\log n)$.

Space analysis counts memory beyond the input, unless a different convention is explicitly stated. An in-place algorithm may use $\Theta(1)$ auxiliary space, while an algorithm that creates a second array of $n$ elements uses $\Theta(n)$ auxiliary space.

4. Recursion and Recurrence Relations

A recursive algorithm calls itself on smaller inputs. Its running time can often be represented by a recurrence relation. A recurrence must include:

1. A recursive rule describing the cost of smaller instances.

2. A base case specifying the cost for sufficiently small input.

4.1 Binary search

Binary search examines a sorted array and discards half the remaining elements after each comparison. Its recurrence is

$$T(n)=T(n/2)+c,$$

where $c$ is a constant cost for the comparison and related work, with $T(1)=d$. Expanding gives

$$T(n)=T(n/2^k)+kc.$$

The recursion reaches a base case when $n/2^k=1$, so $k=\log_2 n$. Therefore,

$$T(n)=\Theta(\log n).$$

Binary search requires sorted data and a representation supporting efficient midpoint access. Searching an array is typically $\Theta(\log n)$; searching a linked list may lose this advantage because reaching a midpoint requires traversal.

4.2 Merge sort

Merge sort divides an array into two halves, recursively sorts both, and merges them in linear time:

$$T(n)=2T(n/2)+cn,$$

with $T(1)=d$. At each recursion level, the total merging cost is $cn$. There are $\log_2 n$ levels, so the total non-base work is $cn\log_2 n$. Hence,

$$T(n)=\Theta(n\log n).$$

A conventional implementation uses $\Theta(n)$ auxiliary space for merging, in addition to recursion-stack space. Merge sort illustrates that time and space must be analyzed separately.

4.3 Master theorem

For recurrences of the form

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

where $a\ge1$, $b>1$, and $f(n)$ is the nonrecursive work, compare $f(n)$ with $n^{\log_b a}$:

If $f(n)$ is polynomially smaller, then $T(n)=\Theta(n^{\log_b a})$.
If $f(n)=\Theta(n^{\log_b a}\log^k n)$ for fixed $k\ge0$, then $T(n)=\Theta(n^{\log_b a}\log^{k+1}n)$.
If $f(n)$ is polynomially larger and satisfies the regularity condition $af(n/b)\le cf(n)$ for some constant $c<1$, then $T(n)=\Theta(f(n))$.

The theorem applies only when the recurrence fits its stated form and conditions. It should not be applied mechanically to arbitrary recurrences.

5. Best, Average, Worst, and Amortized Cases

The best case is the least costly valid input of size $n. The worst case is the most costly valid input. The average case is an expected cost under a specified probability distribution. These are properties of an algorithm together with an input model, not merely labels attached to code.

Worst-case analysis is valuable for systems requiring guarantees, such as real-time control, security-sensitive services, and capacity planning. Average-case analysis may better predict normal workloads but can be invalid if the assumed distribution does not match production data. Best-case analysis is useful for understanding possible behavior but is rarely a sufficient performance guarantee.

Amortized analysis

Amortized analysis determines the average cost per operation over a sequence, even when individual operations vary greatly. It does not assume random inputs. Three standard methods are aggregate analysis, the accounting method, and the potential method.

Consider a dynamic array that doubles its capacity whenever it becomes full. Most insertions cost constant time. Occasionally, an insertion allocates a new array and copies existing elements. For $n$ insertions, copying occurs at capacities $1,2,4,8,\ldots$. The total number of copied elements is bounded by

$$1+2+4+\cdots+2^{k}<2^{k+1},$$

where the final capacity is at least $n$. Thus total copying over $n$ insertions is $O(n)$, and total insertion cost is $O(n)$. The amortized cost per insertion is therefore $O(1)$, even though one particular insertion may cost $\Theta(n)$.

Amortized $O(1)$ does not mean every operation is constant time. It means the total cost of any sufficiently long sequence is linear in the number of operations, under the data structure’s resizing policy.

6. Lower Bounds and Optimality

An upper bound describes what a particular algorithm can do; a lower bound describes what every algorithm must do within a specified computational model and problem definition.

For comparison-based sorting, there are $n!$ possible orderings of $n$ distinct elements. A comparison can distinguish at most two outcomes, so a decision tree of height $h$ has at most $2^h$ leaves. Correct sorting requires at least $n!$ leaves, giving

$$2^h\ge n!,$$

and therefore

$$h\ge \log_2(n!).$$

Using the standard asymptotic estimate $\log(n!)=\Theta(n\log n)$, every comparison-based sorting algorithm has a worst-case lower bound of $\Omega(n\log n)$. Merge sort and heapsort achieve $O(n\log n)$ worst-case time, so they are asymptotically optimal within this model.

This lower bound does not apply to every sorting method. Counting sort and radix sort exploit properties of keys and are not restricted to comparisons. Their performance depends on key ranges, digit representation, and memory requirements. Lower bounds are always conditional on assumptions such as allowed operations, input representation, and required output.

7. Empirical Benchmarking

Asymptotic analysis and measurement answer different questions. Asymptotic analysis predicts scaling under an abstract model; benchmarking measures actual behavior on a particular implementation, machine, compiler, runtime, and workload.

A scientifically useful benchmark should:

1. Define the task, input sizes, and performance metric.

2. Compare equivalent outputs and verify correctness.

3. Use representative and adversarial input distributions.

4. Warm up systems when compilation or caching affects performance.

5. Repeat trials and report variation, not only one timing.

6. Control or record hardware, software versions, clock settings, and concurrency.

7. Separate setup costs from the operation being measured.

8. Measure memory, allocation, throughput, latency, and energy when relevant.

9. Scale input size sufficiently to reveal growth.

10. Avoid drawing universal conclusions from one machine or dataset.

Wall-clock time is affected by operating-system scheduling, garbage collection, cache state, background processes, and input generation. For this reason, a benchmark should use robust summaries such as median or percentile latency when appropriate. Statistical significance is useful, but practical significance matters too: a small speed improvement may not justify substantially greater memory use or implementation complexity.

For AI/ML systems, benchmarking should also consider batch size, accelerator utilization, data-transfer overhead, sparsity, model accuracy, and training convergence. A faster algorithm that produces lower-quality predictions may not be the better engineering choice.

8. Performance Trade-offs in Data Structures and AI/ML

Complexity analysis supports design decisions rather than producing a single universal ranking.

An array offers $\Theta(1)$ indexed access and good cache locality, but insertion in the middle is generally $\Theta(n)$.
A linked list supports local insertion when a node reference is available, but indexed access is $\Theta(n)$ and pointer overhead can harm locality.
A hash table offers expected $\Theta(1)$ lookup under suitable hashing and load-factor assumptions, but worst-case lookup can be $\Theta(n)$ and extra memory is required.
A balanced search tree provides $\Theta(\log n)$ worst-case search, insertion, and deletion while maintaining ordering.
A heap supports finding the minimum or maximum in $\Theta(1)$ and insertion or removal in $\Theta(\log n)$, but does not support fully ordered traversal without additional work.

In machine learning, a brute-force nearest-neighbour query over $n$ vectors with $d$ dimensions commonly requires $\Theta(nd)$ distance work for one query under a straightforward representation. Indexing methods can reduce practical query time, but may use additional memory, incur construction costs, or provide approximate rather than exact neighbours. The appropriate choice depends on query volume, update frequency, dimensionality, latency requirements, and acceptable recall.

A time-space trade-off occurs when extra memory is used to reduce computation. Memoization is a classic example: storing results of overlapping subproblems can reduce repeated computation, often changing exponential time to polynomial time, while requiring storage proportional to the number of subproblems. Caching can similarly reduce latency but introduces invalidation, consistency, and memory-management challenges.

9. Detailed Applied Case: Scaling a Product-Recommendation Service

Background

The following is an illustrative case. An online retailer recommends products similar to a customer’s current selection. The initial prototype stores 200,000 product vectors, each with 128 numerical features, and computes the distance from a query vector to every product.

Problem

The prototype has acceptable latency during testing but becomes slow as the catalogue grows to 20 million products. The team must improve response time without reducing recommendation quality beyond an agreed tolerance.

Analysis

A straightforward exact scan computes a distance for every product. If distance computation examines all 128 features, one query requires $\Theta(nd)$ arithmetic work, where $n$ is the number of products and $d=128$. Increasing $n$ by a factor of 100 therefore increases the dominant computation by approximately a factor of 100, assuming all other factors remain comparable.

The team considers three options:

1. Optimize the exact scan through vectorization and parallel hardware.

2. Build an exact spatial index, whose usefulness may decline in high dimensions.

3. Use an approximate nearest-neighbour index that reduces query work while allowing a controlled reduction in recall.

Approach and solution

The team first establishes a benchmark containing typical queries, difficult queries, catalogue snapshots, and quality labels. It measures p50 and p99 latency, memory use, index-construction time, update cost, and recall at the required number of recommendations.

A vectorized exact scan improves constant factors but retains linear dependence on $n$. An approximate index reduces typical query work and meets the latency target, but requires additional memory and periodic rebuilding. The production design uses the approximate index for online retrieval and an exact method for offline evaluation and selected high-value queries. A monitoring process checks latency, memory, index freshness, and recommendation recall.

Outcome

The selected design satisfies the service-level latency target while preserving the required quality threshold. The improvement does not come from claiming a universally superior Big-O class alone; it comes from matching an algorithmic strategy to workload characteristics, hardware, quality constraints, and operational requirements.

Learning points

A complexity expression must identify the relevant variables.
Constant-factor optimization is valuable but cannot remove a linear dependence on catalogue size.
Approximation creates a quality-performance trade-off that must be measured.
Benchmark design must include realistic workloads and tail latency.
Memory, index construction, update policy, and monitoring are part of algorithm selection.

10. Challenges, Limitations, and Responsible Use

Asymptotic notation suppresses constants, lower-order terms, hardware effects, and implementation details. It can therefore hide important practical differences. Two $\Theta(n)$ algorithms may have very different cache behaviour or allocation rates. Complexity also fails to capture correctness, maintainability, reliability, energy consumption, and fairness.

Worst-case bounds can be overly pessimistic for ordinary workloads, while average-case claims can be misleading when data distributions shift. Randomized algorithms require careful distinction between expected running time and high-probability guarantees. Parallel algorithms require additional measures such as work, span, communication, and synchronization overhead.

In AI systems, performance optimization should not encourage indiscriminate collection or retention of personal data merely to improve caching or benchmarking. Engineers should minimize sensitive data, protect benchmark datasets, document assumptions, and evaluate whether optimization changes access inequities or system reliability. Reproducible experiments and transparent reporting support responsible technical governance.

11. Best Practices

1. Define the input size and computational model before counting operations.

2. State whether a bound is worst-case, expected, amortized, or empirical.

3. Prefer tight $\Theta$ bounds when both upper and lower growth rates are established.

4. Analyze time and auxiliary space separately.

5. Include preprocessing, initialization, and output costs when they matter.

6. Verify recurrence base cases and applicability conditions.

7. Treat average-case results as conditional on an explicit input distribution.

8. Benchmark realistic, adversarial, and scale-relevant workloads.

9. Report hardware, software, repetitions, variability, and correctness checks.

10. Evaluate quality, memory, energy, and maintainability alongside speed.

Chapter Summary

Algorithm analysis explains how computational requirements grow as inputs become larger. Big-O gives an asymptotic upper bound, Big-Ω a lower bound, and Big-Θ a tight bound. Loop structure, recursion, and input representation determine the resulting growth rate. Recurrence relations describe recursive algorithms; binary search is $\Theta(\log n)$ and merge sort is $\Theta(n\log n)$.

Best-case, average-case, and worst-case analyses describe different input conditions, while amortized analysis evaluates the cost of an operation sequence without requiring probabilistic assumptions. Lower bounds establish limits under a specified computational model; the comparison-sorting lower bound of $\Omega(n\log n)$ explains why comparison-based sorting algorithms cannot asymptotically improve beyond that rate. Empirical benchmarking complements theory by measuring implementation behaviour under controlled workloads. Effective engineering combines these perspectives with memory, quality, hardware, operational, ethical, and maintainability considerations.

Key Terms

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

Big-O: Asymptotic upper-bound notation.

Big-Ω: Asymptotic lower-bound notation.

Big-Θ: Tight asymptotic bound.

Input size: A measure of the amount or dimensionality of data processed.

Unit-cost model: An abstract model treating selected basic operations as constant cost.

Time complexity: Growth of computational work with input size.

Space complexity: Growth of memory requirements with input size.

Auxiliary space: Extra memory used beyond the input representation.

Recurrence relation: An equation defining a cost in terms of costs for smaller inputs.

Base case: The nonrecursive stopping condition of a recurrence or recursive algorithm.

Best case: Least costly valid input of a specified size.

Average case: Expected cost under a stated input distribution.

Worst case: Greatest cost among valid inputs of a specified size.

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

Lower bound: A cost that no algorithm can asymptotically improve under stated assumptions.

Benchmark: Controlled empirical measurement of a system or algorithm.

Cache locality: Tendency of computation to reuse nearby memory efficiently.

Trade-off: A design choice in which improving one property worsens or increases another.

Review Questions

Short Answer Questions

1. What is the difference between Big-O and Big-Θ notation?

2. Why must an average-case analysis specify an input distribution?

3. What is auxiliary space?

4. Why is dynamic-array insertion amortized $O(1)$ when resizing uses doubling?

5. State the recurrence and asymptotic time complexity of binary search.

Long Answer Questions

1. Explain how nested loops and logarithmic loops are analyzed, using suitable examples.

2. Derive the $\Theta(n\log n)$ complexity of merge sort using its recurrence.

3. Compare best-case, average-case, worst-case, and amortized analysis.

4. Explain the comparison-based sorting lower bound using a decision-tree argument.

5. Discuss why asymptotic analysis and empirical benchmarking should be used together.

Analytical / Application Questions

B. Ignoring hardware and software versions

C. Checking correctness and repeating trials on representative inputs

D. Measuring setup time without reporting it

Correct Answer: C. Checking correctness and repeating trials on representative inputs

Data Structures and Algorithms
Chapter 2 of 14

Chapter 2 Algorithm and Complexity Analysis