Algorithms, Data Structures, and Complexity

Introduction and Context

Programming in C becomes substantially more powerful when programs are designed around suitable algorithms and data structures. An algorithm specifies a finite, unambiguous sequence of operations for solving a problem; a data structure organizes data so that those operations can be performed efficiently. Complexity analysis provides a principled way to evaluate the time and memory resources required by an implementation.

For postgraduate students, the subject extends beyond memorizing sorting or searching procedures. It involves selecting abstractions, proving correctness, analysing resource trade-offs, understanding implementation constraints in C, and recognizing when an apparently efficient solution fails because of memory hierarchy, input distribution, recursion depth, or concurrency. These issues are important in embedded systems, communication software, compilers, operating systems, signal-processing pipelines, network services, and high-performance computing.

Learning Objectives

After completing this chapter, the reader should be able to:

1. Define algorithms, data structures, abstract data types, and computational complexity.
2. Analyse best-case, average-case, and worst-case time and space requirements.
3. Apply asymptotic notation correctly and distinguish theoretical complexity from practical performance.
4. Implement and evaluate arrays, linked lists, stacks, queues, trees, hash tables, and graphs in C.
5. Select algorithms using correctness, scalability, memory, and reliability criteria.
6. Explain sorting, searching, graph, greedy, divide-and-conquer, and dynamic-programming techniques.
7. Identify implementation hazards involving pointers, allocation, recursion, integer overflow, and undefined behaviour.

1. Algorithms as Problem-Solving Models

An algorithm is a finite procedure that accepts input, produces output, is sufficiently definite for execution, and terminates for every valid input. A program is an implementation of an algorithm in a programming language; it may also include user-interface, error-handling, and system-integration code that is not part of the abstract algorithm.

A sound algorithm has three independent properties:

• Correctness: it produces the required result for every input in the specified domain.
• Termination: it completes after a finite number of steps.
• Efficiency: its resource requirements are acceptable for the intended scale.

Correctness should be established before optimisation. A fast algorithm that produces incorrect results is not an improvement. For complex algorithms, correctness may be argued using invariants, induction, termination measures, or exchange arguments.

Abstract Data Types and Data Structures

An abstract data type (ADT) describes values and permitted operations without prescribing representation. A stack ADT, for example, supports push, pop, and top according to last-in, first-out semantics. It can be implemented using an array or a linked list. A data structure is the concrete representation supporting the ADT.

This distinction promotes encapsulation. A module should expose operations and invariants while hiding fields that clients do not need to manipulate. In C, this can be approximated with an incomplete structure declaration in a header file and a complete definition in the implementation file.

2. Complexity Analysis

Complexity measures how resource usage grows with input size. Let n denote a suitable measure of input size, such as the number of records, vertices, or characters. The two principal resources are running time and auxiliary space.

Asymptotic Notation

Big-O gives an asymptotic upper bound, Big-Ω gives an asymptotic lower bound, and Big-Θ gives a tight asymptotic bound.

Here, f(n) is the measured resource, g(n) is a comparison function, c is a positive constant, and n₀ is a threshold. Big-O ignores constant factors and lower-order terms because the focus is long-run growth. For example, 3n² + 7n + 4 is Θ(n²).

Common growth classes are shown below.

The complexity of a loop is determined by how often its body executes. Nested loops do not automatically imply Θ(n²): if the inner loop doubles an index, its cost may be logarithmic. Similarly, sequential sections add their costs, while the dominant term determines asymptotic growth.

Best, Average, and Worst Cases

The worst-case complexity bounds resource use for every input of size n. Average-case analysis requires a probability distribution over inputs and therefore must state its assumptions. Best-case analysis can be informative but is rarely sufficient for reliability claims. Amortized analysis averages the cost of a sequence of operations without requiring a probability distribution. Dynamic-array insertion, for example, is occasionally expensive when resizing occurs, but its amortized append cost is Θ(1) when capacity grows geometrically.

Space Complexity and Practical Cost

Space complexity includes storage for input, output, and auxiliary data. Some authors report auxiliary space separately. A recursive algorithm may use Θ(log n) stack space even when its explicit data structure is small. In C, memory may reside in static storage, automatic storage (the call stack), or dynamically allocated storage (the heap).

Asymptotic analysis does not capture cache locality, branch prediction, allocation overhead, compiler optimisation, energy use, or real-time deadlines. Thus, empirical measurement and profiling complement, rather than replace, formal analysis. Benchmarking must use representative inputs and report compiler, hardware, optimisation level, and measurement method.

3. Fundamental Linear Data Structures

Arrays and Dynamic Arrays

An array stores elements in contiguous memory. If the base address is b and each element occupies s bytes, the address of element i is conceptually b + i·s, subject to C’s type and object rules. Indexing is Θ(1), and contiguous storage generally gives excellent cache locality. Insertion or deletion near the beginning requires shifting elements and is Θ(n).

C arrays do not store their length automatically. A robust interface passes the length explicitly. Dynamic arrays use a pointer, current length, and capacity. When capacity is exhausted, a larger block is allocated and elements are copied. A growth factor greater than one, commonly two, gives amortized constant append time, although individual resizing remains Θ(n).

Linked Lists

A singly linked list stores a value and a pointer to the next node:

struct Node {
    int value;
    struct Node *next;
};

Insertion after a known node is Θ(1), but finding a position is Θ(n). Nodes need not be contiguous, which facilitates insertion but causes pointer overhead, allocation cost, and poor cache locality. Every allocation must be checked, and every node must eventually be released exactly once.

A doubly linked list adds a prev pointer. It supports constant-time deletion when a node is known, but consumes more memory and creates more pointer-update cases. Sentinel nodes can simplify boundary conditions by eliminating special cases for the first and last elements.

Stacks and Queues

A stack follows last-in, first-out order. It is used for function-call management, expression evaluation, backtracking, and depth-first search. A queue follows first-in, first-out order and is used in buffering, scheduling, breadth-first search, and producer–consumer systems.

A queue implemented with a simple array becomes inefficient if every dequeue shifts all remaining items. A circular buffer avoids shifting: the front and rear indices advance modulo capacity. If the queue holds n items, enqueue and dequeue are Θ(1), subject to a defined full/empty convention.

4. Trees, Heaps, and Hash Tables

Binary Search Trees

A binary search tree (BST) maintains the ordering invariant that keys in the left subtree are smaller than the node key and keys in the right subtree are larger, assuming a chosen duplicate policy. Search, insertion, and deletion take Θ(h), where h is tree height. A balanced tree has h = Θ(log n), while a degenerate tree can have h = Θ(n).

Deletion has three cases: a leaf is removed directly; a node with one child is replaced by that child; and a node with two children is replaced by its inorder successor or predecessor, followed by deletion of that replacement node. Self-balancing trees, such as AVL and red–black trees, maintain logarithmic height through rotations and are appropriate when predictable search performance is needed.

Heaps and Priority Queues

A binary heap is a complete binary tree satisfying a heap-order property. In a min-heap, each parent key is no greater than its children. With zero-based array indexing, the children of index i are 2i + 1 and 2i + 2, when present. The minimum is at the root; insertion and removal are Θ(log n), while inspection is Θ(1). Building a heap from n arbitrary elements using bottom-up heap construction is Θ(n), not Θ(n log n).

Hash Tables

A hash table maps keys to slots using a hash function. Collisions are handled by separate chaining or open addressing. Under a sufficiently uniform hash function and controlled load factor, expected search, insertion, and deletion can be Θ(1); worst-case time is Θ(n). Security-sensitive systems must consider adversarial keys, hash flooding, and denial-of-service risks.

The load factor for a table with m slots and n stored entries is:

This definition is dimensionless. Open addressing generally requires α < 1, and performance degrades as α approaches one. Hash tables do not preserve sorted order and therefore are not a substitute for balanced trees when ordered traversal or range queries are required.

5. Searching and Sorting Algorithms

Searching

Linear search examines elements sequentially and has Θ(n) worst-case time. Binary search requires a sorted random-access sequence. It compares the target with the middle element and discards half the remaining interval. Its worst-case time is Θ(log n), but maintaining sorted order during frequent insertions may cost Θ(n).

A safe C implementation should avoid midpoint overflow by using:

mid = low + (high - low) / 2;

where low and high are valid indices and the calculation is performed in a suitable unsigned or sufficiently wide integer type. The algorithm must define whether duplicates return any occurrence, the first occurrence, or the last occurrence.

Sorting

Insertion sort is adaptive and performs well on small or nearly sorted arrays; its worst-case time is Θ(n²), with Θ(1) auxiliary space. Selection sort is also Θ(n²), but performs few writes. Bubble sort is mainly pedagogical because its general performance is weak.

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

It is stable when the merge chooses the left element first on equal keys, but normally requires Θ(n) auxiliary storage for an array implementation.

Quicksort partitions around a pivot. Its average expected time is Θ(n log n) under suitable pivot and input assumptions, while its worst case is Θ(n²). Randomised or median-oriented pivot selection reduces the likelihood of pathological partitions but does not remove the formal worst-case possibility in ordinary versions. In-place partitioning uses little auxiliary storage, but recursion depth must be controlled.

Heapsort has Θ(n log n) worst-case time and Θ(1) auxiliary array space, but often has poorer cache behaviour than quicksort. A comparison-based sorting algorithm cannot, in the general case, have a worst-case lower bound better than Ω(n log n), because it must distinguish among n! possible orderings. Non-comparison methods such as counting sort can be faster when keys lie in a restricted integer range; their applicability depends on that range and additional memory.

6. Algorithmic Design Paradigms

Divide and Conquer

Divide-and-conquer algorithms divide a problem into smaller independent subproblems, solve them recursively, and combine results. Merge sort is a standard example. The Master Theorem can analyse recurrences of the form:

where a ≥ 1 is the number of subproblems, b > 1 is the reduction factor, and f(n) is the combination work. Its conclusions depend on the relationship between f(n) and n^{log_b a}; the theorem applies only under its stated regularity conditions, so it should not be used mechanically for every recurrence.

Greedy Algorithms

A greedy algorithm makes the locally best choice and never reverses it. Greedy methods are correct only when the problem has an appropriate greedy-choice property and optimal substructure. Kruskal’s and Prim’s minimum-spanning-tree algorithms are examples. A proof may use an exchange argument: show that a locally selected choice can replace the first choice of some optimal solution without reducing quality.

Dynamic Programming

Dynamic programming applies when subproblems overlap and an optimal solution contains optimal solutions to subproblems. It stores results using memoization (top-down) or tabulation (bottom-up). A design should specify the state, recurrence, base cases, evaluation order, and reconstruction method. Space can sometimes be reduced when each state depends only on a small number of previous states, but reconstruction may then require additional information.

Backtracking and Branch-and-Bound

Backtracking explores a decision tree and abandons partial solutions that cannot lead to a valid answer. Branch-and-bound additionally uses bounds to discard branches that cannot improve the best known solution. These methods may have exponential worst-case complexity, but good ordering and pruning can make them effective for constrained practical instances.

7. Graph Algorithms

A graph consists of vertices and edges. It may be directed or undirected, weighted or unweighted, and may contain parallel edges or self-loops depending on the model. An adjacency matrix uses Θ(V²) space and gives constant-time edge lookup; an adjacency list uses Θ(V + E) space and is usually preferable for sparse graphs. Here V is the number of vertices and E the number of edges.

Breadth-first search (BFS) uses a queue and explores vertices by nondecreasing distance from a source in an unweighted graph. With adjacency lists, its time complexity is Θ(V + E). BFS can produce shortest path lengths in edge count. Depth-first search (DFS) uses recursion or an explicit stack and supports cycle detection, topological sorting, and connected-component analysis, also in Θ(V + E).

Dijkstra’s algorithm finds shortest paths from one source when all edge weights are nonnegative. With a binary heap and adjacency lists, a common bound is O((V + E) log V), subject to implementation details. It is not correct for negative-weight edges. Bellman–Ford handles negative edges and detects reachable negative cycles, at a higher cost of O(VE). Floyd–Warshall computes all-pairs shortest paths in Θ(V³) time and Θ(V²) space, making it suitable mainly for relatively small dense graphs.

A minimum spanning tree connects all vertices of a connected, weighted, undirected graph with minimum total edge weight. Kruskal’s algorithm sorts edges and uses a disjoint-set union structure; its typical complexity is O(E log E). Prim’s algorithm grows one tree and can achieve O((V + E) log V) with a binary heap.

8. Correctness, Verification, and C Reliability

An invariant is a statement that remains true at a particular point in every iteration. For a loop, a proof establishes initialization, maintenance, and termination. For example, insertion sort maintains that the prefix before the current index is sorted. At termination, the invariant plus the loop condition implies the desired result.

C provides direct memory access but does not automatically enforce safety. Frequent causes of algorithmic failure include:

• dereferencing null, dangling, or uninitialised pointers;
• accessing an array outside its bounds;
• use-after-free and double-free errors;
• signed integer overflow, which is undefined behaviour;
• incorrect allocation-size calculations;
• failure to check malloc, calloc, or realloc results;
• memory leaks and lost pointers;
• modifying data while an alias is assumed to remain valid.

A safe allocation commonly checks multiplication before computing the byte count. sizeof *ptr is preferable to repeating the pointed-to type because it remains correct if the declaration changes. realloc should normally be assigned to a temporary pointer so that the original allocation is not lost if reallocation fails.

Algorithm design should also specify invalid-input behaviour, duplicate handling, overflow policy, ownership of allocated memory, and thread-safety expectations. Unit tests, property-based tests, assertions, static analysis, sanitizers, and profilers provide complementary evidence; none alone proves complete correctness.

9. Detailed Applied Case: Packet-Event Scheduling in a Communication Node

Background

Consider an illustrative software module in an embedded communication node. Incoming packet events have timestamps, priorities, and identifiers. The processor must repeatedly select the event with the earliest deadline, while newly arriving events are inserted continuously.

Problem

A simple unsorted array allows insertion in Θ(1) but requires Θ(n) time to find the next event. A fully sorted array provides constant-time selection but makes insertion Θ(n). A linked list avoids shifting but still requires a linear scan unless it is maintained in sorted order, in which case insertion remains linear.

Analysis and Solution

A binary min-heap is an appropriate priority queue. Each heap node stores an event and the heap invariant ensures that the earliest deadline is at the root. Insertion uses upward adjustment and costs O(log n); removal uses downward adjustment and costs O(log n); inspection costs Θ(1). If the number of queued events is bounded, a statically allocated array can avoid heap fragmentation and make memory usage predictable—an important real-time consideration.

The implementation must define tie-breaking, for example by comparing (deadline, priority, sequence_number). A monotonic sequence number ensures deterministic ordering among otherwise equal events. If deadlines can wrap around a finite hardware counter, comparisons must use a documented modular-arithmetic rule rather than ordinary signed comparison.

Outcome

The heap reduces selection and insertion from linear time to logarithmic time and provides predictable storage when capacity is fixed. It does not guarantee that every event meets its deadline: interrupt latency, context switching, worst-case execution time, and queue overflow must also be analysed.

Learning Points

1. The best structure depends on the dominant operation pattern.
2. Average-case speed is not sufficient for hard real-time guarantees.
3. Deterministic tie-breaking improves testing and reproducibility.
4. Bounded memory may be preferable to theoretically flexible allocation.
5. Complexity analysis must be combined with hardware and scheduling analysis.

10. Contemporary and Professional Considerations

Modern systems increasingly process streams, graphs, and high-dimensional data. Cache-aware layouts, structure-of-arrays representations, SIMD-friendly loops, external-memory algorithms, and parallel data structures can outperform theoretically equivalent pointer-heavy designs. For very large datasets, I/O complexity and communication cost may dominate arithmetic operations.

AI systems also depend on classical data structures and algorithms: priority queues support search and scheduling, graphs represent knowledge and networks, hash tables support feature dictionaries, and dynamic programming appears in sequence alignment and decoding. AI-generated code must nevertheless be reviewed for complexity, memory ownership, undefined behaviour, data leakage, and licensing constraints.

Ethically responsible engineering includes protecting sensitive data, preventing algorithmic denial of service, documenting assumptions, and testing unusual and adversarial inputs. In safety-critical or regulated systems, traceability from requirements to implementation and verification evidence may be mandatory. Reproducible builds, version control, code review, and clear complexity documentation are professional best practices.

Chapter Summary

Algorithms are finite, precise procedures, while data structures provide concrete organizations of data for efficient operations. Abstract data types separate behavioural contracts from representation. Complexity analysis uses asymptotic notation to describe growth, but practical evaluation must also consider memory locality, allocation, energy, parallelism, and real-time constraints.

Arrays offer fast indexed access and strong locality; linked structures offer flexible insertion but incur pointer and allocation overhead. Stacks, queues, heaps, trees, and hash tables support different operation patterns. Searching and sorting algorithms illustrate trade-offs among ordering requirements, stability, memory, and worst-case guarantees. Graph algorithms require careful attention to representation and edge-weight assumptions. Divide-and-conquer, greedy methods, dynamic programming, and backtracking provide reusable design paradigms, but each depends on specific structural properties.

In C, algorithmic quality is inseparable from memory safety, ownership, integer correctness, and explicit handling of invalid inputs. The appropriate solution is therefore not simply the one with the smallest Big-O expression; it is the one whose correctness, resource bounds, implementation risks, and operational requirements fit the application.

Key Terms

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

Abstract data type: A specification of values and operations independent of representation.

Data structure: A concrete organization of data supporting operations.

Invariant: A property that remains true throughout an algorithmic process.

Big-O: An asymptotic upper-bound notation.

Big-Ω: An asymptotic lower-bound notation.

Big-Θ: A tight asymptotic bound.

Amortized analysis: Analysis of average cost over a sequence of operations.

Recursion: A technique in which a procedure invokes itself on smaller instances.

Array: A contiguous, indexable collection of elements.

Linked list: A node-based sequence connected by pointers.

Stack: A last-in, first-out ADT.

Queue: A first-in, first-out ADT.

Heap: A complete tree satisfying a priority-order property.

Hash table: A key-to-slot structure using a hash function.

Binary search tree: A tree maintaining an ordering relation among keys.

Dynamic programming: Optimisation through stored solutions to overlapping subproblems.

Graph: A set of vertices connected by edges.

Load factor: The ratio of stored entries to hash-table slots.

Cache locality: The performance benefit of accessing nearby memory locations.

Review Questions

5 Short Answer Questions

1. Distinguish an algorithm from a program.
2. What is the difference between Big-O and Big-Θ notation?
3. Why does binary search require sorted data?
4. State one advantage and one disadvantage of linked lists compared with arrays.
5. Why is Dijkstra’s algorithm unsuitable for negative-weight edges?

5 Long Answer Questions

1. Explain arrays, linked lists, stacks, and queues, comparing their representations and operation complexities.
2. Describe merge sort and quicksort, including their recurrence or complexity, stability, memory requirements, and worst-case behaviour.
3. Explain binary search trees, AVL or red–black balancing, and the effect of tree height on performance.
4. Discuss BFS, DFS, Dijkstra’s algorithm, and minimum-spanning-tree algorithms, including their assumptions and graph representations.
5. Explain how C memory-management errors can invalidate an otherwise asymptotically efficient algorithm.

3 Analytical / Application Questions

1. A communication device performs one million queue insertions and removals per second. Compare an unsorted array, sorted array, linked list, and binary heap, and recommend a structure under bounded-memory and predictable-latency requirements.
2. Design a data structure for a dictionary requiring fast exact lookup, ordered traversal, and range queries. Justify whether a hash table, balanced search tree, or combination is most appropriate.
3. An engineer claims that an algorithm with Θ(n log n) complexity is always faster than one with Θ(n²). Critically evaluate the claim using input size, constants, locality, preprocessing, and worst-case versus average-case assumptions.

Multiple Choice Questions with Answers

Question 1

Which operation is Θ(1) for a binary min-heap?

A. Finding the minimum element

B. Removing the minimum element

C. Inserting an arbitrary element

D. Sorting all heap elements

Correct Answer: A. Finding the minimum element

Question 2

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

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: B. Θ(log n)

Question 3

For a hash table with n entries and m slots, which expression defines the load factor?

A. m/n

B. n + m

C. n/m

D. n − m

Correct Answer: C. n/m

Question 4

Which condition is required by Dijkstra’s shortest-path algorithm in its standard form?

A. The graph must be complete

B. All edge weights must be nonnegative

C. The graph must be acyclic

D. Every vertex must have equal degree

Correct Answer: B. All edge weights must be nonnegative

Question 5

What is the adjacency-list space complexity for a graph with V vertices and E edges?

A. Θ(V²)

B. Θ(E²)

C. Θ(V + E)

D. Θ(log V)

Correct Answer: C. Θ(V + E)

Question 6

Which sorting algorithm normally requires Θ(n) auxiliary array space?

A. Merge sort

B. Selection sort

C. Heapsort

D. Insertion sort

Correct Answer: A. Merge sort

Question 7

What is the worst-case time complexity of an unbalanced binary search tree search?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 8

Which technique stores results of overlapping subproblems?

A. Dynamic programming

B. Linear probing only

C. Sequential scanning

D. Sentinel termination

Correct Answer: A. Dynamic programming

Question 9

For T(n) = 2T(n/2) + Θ(n), what is the asymptotic complexity?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: C. Θ(n log n)

Question 10

Which C practice best prevents losing the original allocation when realloc fails?

A. Free the pointer before calling realloc

B. Assign realloc directly to the only pointer

C. Store realloc’s result in a temporary pointer

D. Ignore the return value of realloc

Correct Answer: C. Store realloc’s result in a temporary pointer