Algorithms and Complexity

Introduction

Electrical engineers use algorithms whenever a system must transform input into a reliable output: a controller filters sensor data, a test program searches a fault log, a communication device sorts packets, and a simulation repeatedly evaluates numerical models. Programming syntax is only the implementation medium. The deeper engineering task is to design a procedure that is correct, sufficiently fast, memory-conscious, testable, and appropriate for its operating environment.

An algorithm is a finite, precise sequence of steps that transforms input into output. A program is an implementation of an algorithm in a particular programming language and execution environment. The distinction matters: two programs may implement the same algorithm, while the same program may behave very differently as input size grows.

This chapter develops fundamental algorithms for searching, sorting, traversal, aggregation, and numerical computation. It also introduces correctness reasoning, loop invariants, asymptotic complexity, and engineering trade-offs.

Learning objectives

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

• specify the input, output, assumptions, and termination conditions of an algorithm;
• explain and use Big-O, Big-Ω, and Big-Θ notation;
• reason about correctness using preconditions, postconditions, and loop invariants;
• implement and compare linear search, binary search, elementary sorting algorithms, and efficient sorting algorithms;
• traverse arrays, linked structures, trees, and graphs using breadth-first and depth-first methods;
• design aggregation and numerical algorithms while considering numerical error;
• select an algorithm using time, space, data-structure, reliability, and real-time constraints;
• evaluate algorithms through a realistic engineering case.

1. Describing algorithms precisely

A useful algorithm specification contains five elements:

1. Input: the data supplied, including its type and constraints.
2. Output: the result and its required format.
3. Preconditions: facts assumed to be true before execution.
4. Postconditions: facts guaranteed after successful execution.
5. Termination argument: why the procedure eventually stops.

For example, binary search requires a sorted sequence. Without that precondition, its decisions are not justified, even if the code compiles and sometimes returns the expected result.

An algorithm should also state how it behaves at boundaries. Searching an empty array, traversing a disconnected graph, dividing by a value near zero, and handling duplicate keys are not minor implementation details; they are part of the specification.

Correctness: partial and total

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

A common proof pattern is:

• establish the precondition;
• show that each operation preserves a suitable invariant;
• show that termination implies the postcondition;
• show that a decreasing measure, such as the number of unprocessed elements, guarantees termination.

Loop invariants

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

• Initialization: the invariant is true before the first iteration.
• Maintenance: if it is true before an iteration, it remains true afterward.
• Termination: when the loop ends, the invariant combines with the stopping condition to prove the result.

For a running-sum loop over an array, an appropriate invariant is: “After processing the first i elements, sum equals the sum of those i elements.” This invariant directly establishes correctness when i reaches the array length.

2. Measuring efficiency

Let n denote the input size. The running time of an implementation depends on processor speed, compiler, memory hierarchy, and input values. Complexity analysis instead studies how resource use grows as n increases.

Big-O gives an asymptotic upper bound:

means that there are positive constants c and n₀ such that |f(n)| ≤ c|g(n)| for n ≥ n₀. Big-Ω gives an asymptotic lower bound, and Big-Θ gives a tight asymptotic bound when both an upper and lower bound of the same order apply.

Constants and lower-order terms are omitted because growth dominates for large inputs. For example, 3n² + 5n + 7 is Θ(n²). This does not mean the constants are irrelevant in an embedded system; they can be decisive for small or fixed input sizes.

Common growth rates are:

Complexity may be stated for best, average, or worst cases. Safety-critical and real-time systems generally emphasize worst-case bounds. Average-case claims require an explicit probability model for inputs.

Space complexity includes memory beyond the input representation. An in-place algorithm may use Θ(1) auxiliary space, whereas merge sort normally uses Θ(n) auxiliary storage. Recursion also consumes stack space.

3. Searching algorithms

Linear search

Linear search examines elements sequentially until it finds a target or reaches the end. It works on unsorted data.

linearSearch(A, target):
    for i from 0 to length(A) − 1:
        if A[i] = target:
            return i
    return −1

Its worst-case time is Θ(n), its best case is Θ(1), and its auxiliary space is Θ(1). If the target is equally likely to be at any of n positions and is guaranteed to occur, the average number of comparisons is (n + 1) ÷ 2. If absence is common, unsuccessful searches require n comparisons.

A useful invariant is: before examining position i, none of positions 0 through i − 1 contains the target. Therefore, when the loop terminates unsuccessfully, no array element equals the target.

Binary search

Binary search applies to a sorted random-access sequence. It compares the target with the middle element and discards the half that cannot contain the target.

binarySearch(A, target):
    low = 0
    high = length(A) − 1
    while low ≤ high:
        mid = low + (high − low) // 2
        if A[mid] = target: return mid
        if A[mid] < target: low = mid + 1
        else: high = mid − 1
    return −1

The expression for mid avoids overflow that can occur with (low + high) ÷ 2 when integer limits are finite. The worst-case number of iterations is Θ(log n), and auxiliary space is Θ(1) for the iterative version.

Its invariant is that, if the target occurs, it lies within the inclusive interval [low, high]. Each iteration preserves this property while reducing the interval. Binary search is unsuitable for unsorted data and is less attractive on a linked list because locating the middle is not constant time.

When duplicate values exist, ordinary binary search may return any matching index. Variants can find the first or last occurrence by continuing after a match.

4. Sorting algorithms

Sorting arranges records according to a key. A stable sort preserves the relative order of records with equal keys. Stability is valuable when records have previously been sorted by a secondary key.

Selection sort

Selection sort repeatedly finds the smallest remaining element and places it at the next output position. It performs Θ(n²) comparisons, uses Θ(1) auxiliary space, and typically performs few swaps. It is useful when writes are expensive and n is small, but it is not stable in its usual form.

Insertion sort

Insertion sort maintains a sorted prefix and inserts each next element into its correct position. Its worst-case time is Θ(n²), best-case time is Θ(n) when the data is already sorted, and auxiliary space is Θ(1). It is stable and often excellent for small or nearly sorted arrays.

The invariant is: before processing position i, positions 0 through i − 1 are sorted and contain exactly the original prefix elements. Shifting larger elements right creates the insertion location without losing data.

Merge sort

Merge sort divides the sequence into two halves, recursively sorts each half, and merges the sorted halves. Its recurrence is:

Under the usual comparison and array assumptions, this yields Θ(n log n) time in best, average, and worst cases. Standard array-based merge sort uses Θ(n) auxiliary space and is stable. Its predictable time makes it attractive when worst-case performance matters.

Quicksort

Quicksort selects a pivot, partitions the data into smaller and larger elements, and recursively sorts the partitions. With balanced partitions, its time is Θ(n log n); with repeatedly extreme pivots, worst-case time is Θ(n²). Randomized pivot selection or a robust pivot strategy reduces the likelihood of poor behavior but does not eliminate the worst-case possibility unless additional safeguards are used.

Quicksort often has excellent cache behavior and can use little auxiliary storage, but partitioning and recursion require careful implementation. A three-way partition is useful when many keys are equal.

Choosing a sorting algorithm

Non-comparison methods can be faster than Θ(n log n), but only because they exploit additional assumptions about keys, such as bounded integer ranges or fixed digit representations.

5. Traversal and aggregation

Array aggregation

Aggregation computes a summary such as a sum, minimum, maximum, count, or average. A one-pass sum has Θ(n) time and Θ(1) auxiliary space. For an average, the mathematical definition is:

where n > 0 and xᵢ are numerical observations in consistent units. An implementation should define behavior for n = 0 and consider overflow. Summing large floating-point values can lose precision; compensated summation can reduce, but not entirely eliminate, rounding error.

For streaming data, an aggregate may be updated incrementally. If sₖ is the sum of the first k values, then:

This avoids storing every observation, but it does not automatically solve numerical stability or missing-data policy.

Tree traversal

A binary tree can be traversed in preorder (root, left, right), inorder (left, root, right), or postorder (left, right, root). In a binary search tree, inorder traversal produces keys in nondecreasing order. Every node is visited once, so traversal time is Θ(n); auxiliary space is Θ(h), where h is tree height, due to recursion or an explicit stack.

Graph traversal

Graphs model circuits, communication networks, dependencies, and physical connectivity. Breadth-first search (BFS) uses a queue and explores vertices by distance in edges. In an unweighted graph represented by adjacency lists, BFS runs in Θ(V + E), where V is the number of vertices and E is the number of edges. It produces shortest path lengths measured in edges.

Depth-first search (DFS) uses recursion or a stack. It also runs in Θ(V + E) with adjacency lists and supports cycle detection, connected-component discovery, and topological ordering in directed acyclic graphs.

A visited set is essential. Without it, a cycle can cause nontermination. For disconnected graphs, start a new traversal from every unvisited vertex.

6. Numerical algorithms and engineering reliability

Numerical algorithms approximate mathematical quantities using finite-precision arithmetic. Correctness therefore includes both algorithmic logic and error behavior.

Bisection for a root

To solve f(x) = 0, bisection requires a continuous function on [a, b] with f(a)f(b) ≤ 0. If the signs are opposite, continuity guarantees at least one root in the interval. Repeatedly evaluate the midpoint m = (a + b) ÷ 2 and retain the half interval containing a sign change.

After k iterations, the interval width is:

Thus, to ensure widthₖ ≤ ε, it is sufficient that:

where ε > 0 is the desired width. Bisection is robust and has predictable convergence, but it is slower than methods such as Newton’s method when derivatives are reliable and the initial estimate is appropriate.

Newton’s method

Newton’s iteration is:

It requires a differentiable function and a nonzero derivative at the current estimate. Near a simple root and under suitable regularity conditions, convergence is often quadratic, but poor initial values, zero derivatives, or discontinuities can cause divergence. Engineering software should impose iteration limits and stopping criteria based on residual size, step size, or both.

7. Detailed application: monitoring an electrical distribution panel

Background

Consider an illustrative embedded monitoring unit that records the identifiers and temperatures of circuit branches. The device must detect an over-temperature condition, report the highest temperature, and locate a branch by identifier.

Problem

The controller receives up to 2,000 records per sampling cycle. Records arrive in identifier order only during commissioning; during normal operation they are not guaranteed to be sorted. The response deadline is 20 ms, and RAM is limited.

Analysis

A linear scan can detect the maximum temperature in Θ(n) time and Θ(1) auxiliary space. Searching by identifier is also Θ(n) with linear search. If identifiers are searched hundreds of times per cycle, repeatedly scanning is wasteful. Sorting once and using binary search costs Θ(n log n) for sorting plus Θ(log n) per query, but it requires maintaining sorted records and handling updates.

An alternative is a hash table, which normally provides expected Θ(1) lookup but requires extra memory and careful collision handling. If worst-case predictability is more important than average speed, a sorted array with binary search may be preferable.

Approach

The design uses:

• a one-pass aggregation for maximum temperature;
• insertion sort during commissioning because the data is nearly sorted and the set is small;
• binary search during stable operating periods;
• a linear scan as a fallback after an update invalidates the sorted order;
• explicit checks for empty input, invalid temperatures, and duplicate identifiers.

The maximum-temperature invariant is: after processing the first i records, maxTemp is the greatest valid temperature among those records. At termination, it is the greatest valid temperature in the complete input.

Outcome

For 2,000 records, one aggregation pass remains linear and uses constant auxiliary storage. Replacing 500 repeated linear searches with binary searches substantially reduces comparisons when the sorted representation is maintained. However, the design does not blindly choose the asymptotically fastest method: update frequency, memory, deadline guarantees, data validity, and implementation complexity determine the final choice.

Learning points

1. Input properties determine which algorithms are valid.
2. A lower asymptotic order is not the only engineering criterion.
3. Invariants make safety checks and testing more systematic.
4. Data-structure maintenance costs must be included in the analysis.

8. Trade-offs, testing, and professional practice

Algorithm selection should consider worst-case latency, average throughput, memory, energy, code size, numerical stability, maintainability, and failure behavior. In a battery-powered sensor, a slightly slower algorithm may be preferable if it reduces memory traffic or permits lower clock frequency. In a protection relay, a predictable upper bound may be more important than average performance.

Testing should include normal, boundary, adversarial, and invalid inputs: empty sequences, one-element sequences, duplicates, already sorted and reverse-sorted data, extreme numeric values, disconnected graphs, cycles, and missing records. Property-based tests are especially useful. For example, a sorting implementation should return a sequence in nondecreasing order containing exactly the original multiset of elements.

Algorithmic complexity can become a security issue. An attacker who controls input may deliberately trigger worst-case quicksort behavior or excessive graph exploration. Input limits, randomized strategies, timeouts, and robust data structures reduce such risks. Engineers must also avoid inappropriate automation: AI-generated code should be reviewed, tested, and checked against the stated invariants and complexity claims rather than accepted because it appears plausible.

Chapter Summary

Algorithms are precise procedures whose quality depends on correctness, termination, resource use, and suitability for context. Preconditions and postconditions define what an algorithm promises; loop invariants provide a practical method for proving iterative correctness. Big-O, Big-Ω, and Big-Θ describe asymptotic growth, while engineering decisions must also consider constants, memory, cache behavior, numerical error, and worst-case deadlines.

Linear search works without ordering and takes Θ(n) time. Binary search takes Θ(log n) time but requires sorted, efficiently indexed data. Selection and insertion sort are simple Θ(n²) methods with useful small-input properties. Merge sort provides stable Θ(n log n) performance with additional memory, while quicksort often performs well but has a Θ(n²) worst case. BFS and DFS traverse adjacency-list graphs in Θ(V + E). Aggregation is commonly one-pass and linear. Bisection offers robust numerical convergence, whereas Newton’s method can be faster but requires stronger assumptions.

Professional algorithm design combines formal reasoning, empirical testing, data-structure choice, resource analysis, and awareness of reliability and security constraints.

Key Terms

Algorithm: A finite, precise procedure for solving a problem.

Asymptotic analysis: Study of resource growth as input size increases.

Big-O: An asymptotic upper bound.

Big-Ω: An asymptotic lower bound.

Big-Θ: A tight asymptotic bound.

Precondition: Requirement that must hold before execution.

Postcondition: Property guaranteed after successful execution.

Loop invariant: A statement preserved across loop iterations.

Termination: Property that an algorithm eventually stops.

Linear search: Sequential examination of elements.

Binary search: Halving search on sorted indexed data.

Stable sort: Sort preserving the order of equal-key records.

In-place algorithm: Algorithm using little auxiliary storage.

Breadth-first search: Queue-based graph traversal by distance layers.

Depth-first search: Stack- or recursion-based graph traversal.

Aggregation: Computation of a summary over data.

Numerical stability: Resistance of an algorithm to amplification of numerical error.

Bisection: Bracketing root-finding method based on interval halving.

Worst-case complexity: Maximum resource use over permitted inputs.

Review Questions

Short Answer Questions

1. What is the difference between a program and an algorithm?
2. State the three parts of a loop-invariant proof.
3. Why does binary search require sorted data?
4. What does it mean for a sorting algorithm to be stable?
5. What are the time and auxiliary-space complexities of linear search?

Long Answer Questions

1. Compare insertion sort, merge sort, and quicksort in terms of time complexity, space, stability, and engineering use.
2. Explain BFS and DFS, including their data structures, complexity, and typical applications.
3. Develop and justify a loop invariant for computing the maximum of an array.
4. Explain why asymptotic complexity alone is insufficient for selecting an embedded-systems algorithm.
5. Compare bisection and Newton’s method for solving f(x) = 0, including assumptions and failure modes.

Analytical / Application Questions

1. A controller performs 1,000 identifier lookups in an array of 10,000 unsorted records. Compare the likely work of repeated linear search with sorting once and using binary search. State assumptions that affect the decision.
2. Design a graph-traversal method for identifying disconnected sections of an electrical network. Specify the representation, visited-state handling, complexity, and how cycles are treated.
3. A numerical routine sometimes divides by a derivative close to zero. Analyze why Newton’s method may fail and propose a robust hybrid strategy using safeguards or bisection.

Multiple Choice Questions with Answers

Question 1

Which precondition is required for ordinary binary search?

A. The data must be stored in a linked list

B. The data must be sorted

C. All elements must be distinct

D. The data must contain only integers

Correct Answer: B. The data must be sorted

Question 2

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

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 3

Which sorting algorithm is normally stable and has worst-case Θ(n log n) time?

A. Merge sort

B. Selection sort

C. Basic quicksort

D. Binary search

Correct Answer: A. Merge sort

Question 4

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

A. The program uses no memory

B. The invariant remains true after an iteration

C. The input is sorted before execution

D. The loop executes exactly n times

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

Question 5

With adjacency-list representation, what is the time complexity of BFS?

A. Θ(log V)

B. Θ(V) only

C. Θ(E²)

D. Θ(V + E)

Correct Answer: D. Θ(V + E)

Question 6

Which method is generally appropriate for finding a root when f is continuous and a sign change is bracketed?

A. Bisection

B. Selection sort

C. Linear search

D. DFS

Correct Answer: A. Bisection

Question 7

What is the usual worst-case time complexity of quicksort?

A. Θ(1)

B. Θ(log n)

C. Θ(n²)

D. Θ(2ⁿ)

Correct Answer: C. Θ(n²)

Question 8

What does an inorder traversal of a binary search tree produce?

A. Keys in nondecreasing order

B. Keys in random order

C. Only leaf nodes

D. A breadth-first sequence

Correct Answer: A. Keys in nondecreasing order

Question 9

For a one-pass sum of n values, what is the auxiliary-space complexity when only the running sum is stored?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 10

Which statement about Newton’s method is correct?

A. It never requires a derivative

B. It always converges from every starting value

C. It can converge rapidly but may fail with poor starting values or near-zero derivatives

D. It applies only to sorted arrays

Correct Answer: C. It can converge rapidly but may fail with poor starting values or near-zero derivatives