Algorithms, Data Structures, and Complexity

Introduction

Software programs rarely fail because a programmer cannot write a loop or conditional statement. They fail because data is represented poorly, operations are inefficient, or an algorithm does not correctly handle all valid inputs. Algorithms and data structures therefore form the practical foundation of software engineering.

An algorithm is a finite, unambiguous sequence of steps that transforms input into output and terminates after a finite number of steps. A data structure is a systematic way of organizing data so that required operations—such as insertion, deletion, searching, and traversal—can be performed correctly and efficiently.

The same problem may have several correct algorithms with very different performance. Searching an unsorted list by examining each element is simple and general, while binary search is much faster but requires sorted data and indexed access. Similarly, a queue can be implemented using an array, linked nodes, or a library container. The choice affects speed, memory use, flexibility, and reliability.

This chapter develops the principal data structures and algorithms required at diploma level, with examples applicable to C++, Java, and Python. Complexity is expressed mainly using Big-O notation. The objective is not merely to memorize classifications, but to select and implement appropriate structures for real software systems.

Learning Objectives

After completing this chapter, a student should be able to:

1. Explain the relationship between algorithms, data structures, correctness, and efficiency.
2. Implement linear and binary search and compare their assumptions and performance.
3. Implement and analyse common sorting algorithms.
4. Use stacks and queues to model practical computational processes.
5. Explain and implement linked lists, trees, and hash-based structures.
6. Apply Big-O, Big-Ω, and Big-Θ notation to time and space analysis.
7. Select an appropriate data structure for a given application.
8. Test algorithms using boundary cases and reason about their correctness.

1. Algorithms, Inputs, and Correctness

A useful algorithm has five characteristics:

• Input: zero or more externally supplied values.
• Output: at least one result or observable effect.
• Definiteness: every step is precisely specified.
• Finiteness: execution eventually terminates for every valid input.
• Effectiveness: each operation is sufficiently basic to be carried out.

Correctness has two dimensions. Partial correctness means that if an algorithm terminates, its result is correct. Total correctness additionally requires termination for every valid input. For example, a loop that searches a list must both identify a matching item correctly and stop when the item is absent.

A practical proof technique is the loop invariant: a statement that remains true before and after each loop iteration. For linear search, the invariant can be stated as: “Before examining position i, no position from 0 through i − 1 contains the target.” If the loop ends because the target is found, the result is correct. If it reaches the end, the invariant establishes that the target is absent.

Good implementations also define behaviour for empty input, duplicate values, invalid indexes, full structures, and missing keys. These boundary conditions are often where defects occur.

2. Measuring Efficiency

The running time of a program depends on the input size and sometimes on the arrangement of input values. Let n denote the number of input elements. Instead of measuring seconds on one computer, algorithm analysis counts the growth of fundamental operations as n increases.

2.1 Asymptotic notation

• Big-O, O(f(n)), gives an asymptotic upper bound: the work grows no faster than a constant multiple of f(n) for sufficiently large n.
• Big-Ω, Ω(f(n)), gives an asymptotic lower bound.
• Big-Θ, Θ(f(n)), gives a tight asymptotic bound when both upper and lower bounds have the same growth rate.

For example, a loop that visits every element once performs n iterations and has time complexity Θ(n). Two nested loops that each process n elements generally perform n² iterations and have complexity Θ(n²).

Constants and lower-order terms are ignored in asymptotic analysis. Thus 4n + 12 is Θ(n), while 3n² + 5n + 7 is Θ(n²). This does not mean constants are irrelevant in practice: a Θ(n) algorithm with expensive operations may be slower than a Θ(n log n) algorithm for small inputs.

2.2 Common growth rates

If an algorithm uses an auxiliary array containing n values, its auxiliary space is Θ(n). Variables holding a fixed number of values require Θ(1) auxiliary space. Input storage itself is normally distinguished from extra working storage.

2.3 Best, average, and worst cases

The best case is the most favourable valid input, the worst case is the least favourable, and the average case depends on an assumed probability distribution. Worst-case analysis is often preferred in safety-critical or service-level contexts because it provides a guarantee. Average-case claims must state their assumptions; they are not automatically valid for every data set.

3. Searching Algorithms

3.1 Linear search

Linear search examines elements sequentially until the target is found or the collection ends.

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

For an array of n elements, the best case is Θ(1), when the first element matches. The worst case is Θ(n), when the target is last or absent. Its auxiliary space is Θ(1). Linear search works on unsorted data and is appropriate for small collections or one-off searches.

3.2 Binary search

Binary search requires a sorted sequence and efficient access to its middle element. It compares the target with the middle value 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
        else if A[mid] < target:
            low = mid + 1
        else:
            high = mid − 1
    return −1

After k iterations, at most n/2ᵏ values remain. The search terminates when n/2ᵏ ≤ 1, so k is approximately log₂ n. Therefore binary search has worst-case time Θ(log n), best-case time Θ(1), and iterative auxiliary space Θ(1). A recursive version normally uses Θ(log n) call-stack space.

Binary search is not automatically suitable for linked lists because finding the middle node is not constant time. It is most effective on sorted arrays or other structures with random access.

4. Sorting Algorithms

Sorting arranges values according to an ordering relation, such as ascending numerical order or lexicographic string order. A sorting algorithm is stable if equal-key records retain their original relative order. Stability matters when records have multiple ordering criteria.

4.1 Selection sort

Selection sort repeatedly selects the smallest remaining element and places it at the next output position.

for i from 0 to n − 2:
    smallest = i
    for j from i + 1 to n − 1:
        if A[j] < A[smallest]:
            smallest = j
    swap A[i] and A[smallest]

It performs Θ(n²) comparisons in best, average, and worst cases, uses Θ(1) auxiliary space, and is generally not stable. It can be useful when memory is restricted and the number of swaps should be small.

4.2 Insertion sort

Insertion sort maintains a sorted prefix and inserts each new element into its correct position.

for i from 1 to n − 1:
    item = A[i]
    j = i − 1
    while j >= 0 and A[j] > item:
        A[j + 1] = A[j]
        j = j − 1
    A[j + 1] = item

Its best-case time is Θ(n) when the input is already sorted. Average and worst-case time are Θ(n²). It uses Θ(1) auxiliary space and is stable when the comparison is strictly greater than. Insertion sort is often effective for small or nearly sorted inputs.

4.3 Merge sort

Merge sort divides the sequence into halves, recursively sorts each half, and merges the sorted halves. The merge operation takes linear time. Its recurrence is:

The two recursive calls process halves and the merge processes all n elements. This gives Θ(n log n) time in best, average, and worst cases. Standard array-based merge sort requires Θ(n) auxiliary space. It is stable and has predictable performance, making it useful when worst-case guarantees matter.

4.4 Quicksort

Quicksort selects a pivot, partitions values into smaller and larger groups, and recursively sorts the groups. A balanced partition gives:

A repeatedly extreme pivot gives:

Thus average time is commonly Θ(n log n), but worst-case time is Θ(n²). Randomized pivot selection or a carefully designed pivot strategy reduces the likelihood of poor partitions, but does not remove the theoretical worst case. In-place implementations can use little extra array storage, although recursive stack space is typically Θ(log n) on balanced partitions and Θ(n) in the worst case. Quicksort is not generally stable.

4.5 Choosing a sorting algorithm

Production languages often provide optimized library sorting algorithms. Using a tested library implementation is normally preferable to writing a new sort unless the educational, performance, or domain requirements justify it.

5. Stacks and Queues

5.1 Stacks

A stack is a last-in, first-out (LIFO) structure. Its principal operations are:

• push: add an item to the top;
• pop: remove and return the top item;
• peek/top: inspect the top item without removing it;
• isEmpty: test whether no items are present.

An array implementation maintains a top index. A linked implementation places new nodes at the head. With suitable design, push, pop, and peek are Θ(1). Popping an empty stack is an underflow error; pushing into a fixed-capacity array stack may cause overflow.

Stacks support function-call management, undo operations, expression evaluation, depth-first search, syntax matching, and backtracking. Parenthesis matching is a typical application: opening symbols are pushed, and each closing symbol must match the most recently opened symbol.

5.2 Queues

A queue is a first-in, first-out (FIFO) structure. Its operations are enqueue, dequeue, front/peek, and isEmpty. Queues model print jobs, customer service, network buffers, and breadth-first graph traversal.

A naive array queue that shifts every remaining element after dequeue has Θ(n) dequeue time. A circular queue avoids shifting by maintaining front and rear positions modulo the capacity. Its enqueue and dequeue operations are Θ(1), provided capacity management is handled correctly.

A linked queue maintains pointers to both the front and rear nodes. Enqueue adds after rear, and dequeue removes front; both are Θ(1). If the rear pointer is omitted, enqueue may require scanning the entire list and become Θ(n).

6. Linked Structures

An array stores elements in contiguous indexed positions. A linked structure stores nodes connected by references. A singly linked node contains a value and a reference to the next node.

class Node:
    value
    next

Inserting at the head is Θ(1): create a node, point it to the current head, and update head. Deleting the head is also Θ(1). Searching for a value is Θ(n). Inserting after a known node is Θ(1), but locating that node may cost Θ(n). A doubly linked list adds a previous reference, allowing traversal in both directions and easier deletion when a node reference is already available, at the cost of additional memory.

Linked structures are useful when frequent insertions and deletions occur at known positions or when the collection size changes regularly. They have disadvantages: extra reference storage, poor cache locality, no constant-time random access, and more opportunities for reference errors. A robust implementation must update all relevant links and define behaviour for an empty list, a one-node list, and deletion of the head or tail.

7. Trees

A tree is a connected, acyclic hierarchical structure. In a rooted tree, the top node is the root, nodes may have children, and a node with no children is a leaf. The depth of a node is the number of edges from the root. The height of a tree is the maximum node depth.

7.1 Binary search trees

A binary search tree (BST) has at most two children per node and obeys the ordering rule: keys in the left subtree are smaller than the node key, and keys in the right subtree are larger, assuming a distinct-key policy. An in-order traversal visits keys in sorted order.

Searching, insertion, and deletion take Θ(h), where h is the tree height. A balanced tree has h = Θ(log n), so these operations are Θ(log n). If inserting already sorted values into an ordinary unbalanced BST, the tree can become a chain with h = Θ(n), making operations Θ(n).

Deletion has three cases: deleting a leaf, deleting a node with one child, and deleting a node with two children. In the last case, the node can be replaced by its in-order successor or predecessor, followed by deletion of that replacement node.

Self-balancing trees, such as AVL and red-black trees, maintain height Θ(log n) through rotations. They provide predictable search and update performance but require more complex implementation.

7.2 Tree traversal

• Pre-order: root, left subtree, right subtree; useful for copying or prefix representations.
• In-order: left subtree, root, right subtree; yields sorted order in a BST.
• Post-order: left subtree, right subtree, root; useful for deleting a tree or evaluating expression trees.
• Level-order: visit depth by depth using a queue.

Recursive traversal uses call-stack space proportional to tree height. For a balanced tree this is Θ(log n); for a chain it is Θ(n).

8. Hash-Based Structures

A hash table stores key–value pairs using a hash function. The function maps a key to an array index:

Here, h(key) is a non-negative hash value and m is the number of table slots. The modulo operation is appropriate when the table uses m indexed slots. A good hash function distributes likely keys uniformly and deterministically: equal keys must produce equal hash values.

Different keys can map to the same slot, producing a collision. Two standard collision strategies are:

1. Separate chaining: each slot refers to a list or other container of entries. The expected operation time is Θ(1 + α), where α = n/m is the load factor, under uniform hashing. In the worst case, all keys collide and operations become Θ(n).
2. Open addressing: every entry is stored in the table itself. Probing sequences—such as linear probing—identify alternative slots. Performance declines as the table becomes full, so resizing is important.

Hash tables offer expected Θ(1) search, insertion, and deletion under suitable hash distribution and controlled load factor. These are expected rather than unconditional guarantees. Ordered traversal is not naturally provided; if sorted keys are required, a tree or sorting step may be preferable.

When comparing keys, hash-table implementations must respect equality and hashing contracts. In Java, equal objects must have equal hash codes. In Python, objects used as dictionary keys must have stable hashing and equality behaviour while stored. Mutable key fields that affect hashing can make entries effectively unreachable.

9. Selecting a Data Structure

Selection should begin with required operations rather than with a favourite implementation language. The following questions are useful:

• Is indexed access required?
• Are insertions and deletions frequent, and where do they occur?
• Must data remain sorted?
• Are duplicate keys allowed?
• Is predictable worst-case performance required?
• Is memory limited?
• Is iteration order significant?
• Are keys immutable and hashable?

No structure is universally optimal. A hash table may outperform a tree for exact key lookup, while a tree is better for range queries such as “all values between 100 and 200.”

10. Worked Example: Choosing and Analysing a Student-Record Index

Consider a college system that stores student records identified by unique student number. The system performs 95% exact lookups, 3% insertions, and 2% requests for students within a number range. The records must also be displayed in ascending student-number order.

A hash table is attractive for the dominant exact-lookup workload, offering expected Θ(1) lookup and insertion. However, it does not naturally support ordered range queries or sorted traversal. A balanced search tree offers Θ(log n) worst-case lookup, insertion, and range navigation, while maintaining order.

A practical design is therefore either:

• a balanced tree as the primary index, if predictable performance and range queries are important; or
• a hash table for exact lookup combined with a separate ordered index, if the additional memory and update cost are justified.

The second design duplicates indexing information and requires consistency whenever a record changes. The first design is simpler and may be preferable for a diploma-level application. The decision should be validated with realistic measurements, not based solely on asymptotic notation.

Illustrative implementation strategy

For a tree index, each node stores student number, a reference to the record, left and right children, and balancing metadata if a self-balancing tree is used. Lookup follows comparisons from the root. A range query finds the first relevant node and performs an ordered traversal, pruning subtrees outside the requested range.

Correctness depends on maintaining the ordering invariant after every insertion and deletion. Testing should include an empty index, one record, duplicate student numbers, ascending insertions, descending insertions, absent keys, and a range containing no records. Performance tests should vary n and measure both ordinary and adversarial insertion orders.

11. Testing, Reliability, and Professional Practice

Algorithm testing should include:

• normal cases;
• boundary cases, such as empty and one-element inputs;
• duplicate values;
• already sorted and reverse-sorted data;
• maximum permitted sizes;
• invalid operations, such as dequeue from an empty queue;
• randomized tests compared with a trusted reference implementation.

Assertions can document invariants, such as “the stack size is never negative” or “the BST ordering property holds.” Complexity claims should be checked against implementation details. For example, a queue advertised as Θ(1) dequeue is not actually so if its implementation shifts n − 1 elements after each removal.

Security is also relevant. Poor hash functions can permit deliberate collision attacks, causing severe performance degradation. Untrusted input should not be allowed to trigger uncontrolled recursion, excessive memory allocation, or worst-case algorithmic behaviour. Library implementations should be preferred where they have undergone extensive testing and security review.

AI-assisted programming can generate plausible implementations of sorting, trees, and hash tables, but generated code must be reviewed. Common defects include incorrect boundary conditions, failure to update both links in a doubly linked list, incorrect handling of duplicate keys, and claims of constant-time performance for operations that scan a structure. Professional responsibility remains with the developer.

12. Contemporary Developments and Limitations

Modern systems increasingly use hybrid structures. Databases combine hash indexes, B-trees, caches, and logs. Distributed systems use partitioning and consistent hashing to spread keys among machines. Concurrent queues and lock-free structures address parallel workloads but introduce memory-ordering and synchronization concerns beyond the scope of basic implementations.

Asymptotic analysis has limitations. It ignores constants, hardware caches, memory latency, input distribution, concurrency, and implementation overhead. A linked list and an array may both support Θ(n) search, yet the array often performs better because contiguous memory improves cache locality. Consequently, sound engineering combines theoretical analysis, profiling, workload modelling, and testing.

Chapter Summary

Algorithms are finite, precise procedures for solving problems, while data structures organize data to support operations efficiently. Correctness requires both a valid result and termination; invariants provide a useful way to reason about loops and structures.

Big-O describes asymptotic upper growth, Big-Ω lower growth, and Big-Θ tight growth. Linear search works on unsorted data in Θ(n) worst-case time, whereas binary search requires sorted random-access data and runs in Θ(log n). Selection and insertion sorts are generally Θ(n²), while merge sort provides Θ(n log n) worst-case performance and quicksort commonly provides Θ(n log n) average performance but Θ(n²) worst-case performance.

Stacks implement LIFO behaviour and queues implement FIFO behaviour. Linked structures support flexible insertion and deletion but do not provide efficient random access. Binary search trees provide ordered operations whose cost depends on height; balanced trees maintain Θ(log n) height. Hash tables provide expected Θ(1) key operations under appropriate hashing and load conditions, but collisions can produce linear worst-case behaviour.

Professional selection considers required operations, ordering, memory, predictability, workload, and security. Complexity analysis is essential, but it should be combined with correctness proofs, boundary testing, profiling, and careful use of trusted libraries.

Key Terms

Algorithm: A finite, precise procedure that transforms input into output.

Data structure: An organization of data designed to support operations efficiently.

Correctness: The property that an algorithm produces the specified result for valid input.

Loop invariant: A statement that remains true throughout loop execution.

Big-O: An asymptotic upper-bound notation for growth of resource use.

Big-Ω: An asymptotic lower-bound notation.

Big-Θ: A tight asymptotic bound.

Linear search: Sequential examination of elements until a target is found or input ends.

Binary search: Search by repeatedly halving a sorted, random-access range.

Stable sort: A sort that preserves the relative order of equal-key records.

Stack: A last-in, first-out data structure.

Queue: A first-in, first-out data structure.

Linked list: A sequence of nodes connected by references.

Tree: A connected, acyclic hierarchical data structure.

Binary search tree: A binary tree organized according to key ordering.

Height: The maximum number of edges from a tree root to a leaf.

Hash function: A deterministic function that maps a key to a hash value.

Collision: A situation in which different keys map to the same hash-table slot.

Load factor: The ratio of stored entries to hash-table slots, α = n/m.

Auxiliary space: Extra working memory used apart from the input representation.

Review Questions

Short Answer Questions

1. What is the difference between an algorithm and a data structure?
2. Why does binary search require sorted data?
3. State the ordering behaviour of a stack and a queue.
4. What is a collision in a hash table?
5. Why can an ordinary binary search tree have Θ(n) operations?

Long Answer Questions

1. Explain Big-O, Big-Ω, and Big-Θ notation and illustrate each with an algorithmic example.
2. Compare insertion sort, merge sort, and quicksort in terms of time complexity, space, stability, and suitable applications.
3. Describe how a circular queue avoids the inefficiency of shifting elements after each dequeue.
4. Explain the three deletion cases in a binary search tree and discuss the effect of tree height on performance.
5. Compare separate chaining and open addressing as collision-resolution strategies.

Analytical / Application Questions

1. A program repeatedly searches an unchanging collection of one million sorted records. Should it use linear search, binary search, a balanced tree, or a hash table? Justify the choice, including any preprocessing considerations.
2. Design a data structure for a browser’s undo feature and explain the operations, complexity, and behaviour when no undo operation is available.
3. A queue implementation removes the front item by shifting every remaining array element one position left. Analyse its dequeue complexity and propose an improved implementation.

Multiple Choice Questions with Answers

Question 1

Which notation describes the worst-case time of binary search on a sorted array?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 2

Which data structure follows last-in, first-out ordering?

A. Queue

B. Stack

C. Hash table

D. Binary search tree

Correct Answer: B. Stack

Question 3

What is the worst-case time complexity of quicksort with repeatedly extreme pivot choices?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²)

Correct Answer: D. Θ(n²)

Question 4

Which condition is required for ordinary binary search?

A. The data must be stored in a linked list

B. The data must be sorted and efficiently indexable

C. All values must be unique

D. The data must be stored in a hash table

Correct Answer: B. The data must be sorted and efficiently indexable

Question 5

What is the expected search complexity of a well-designed hash table with controlled load factor?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 6

Which traversal of a binary search tree produces keys in sorted order?

A. Pre-order

B. Post-order

C. In-order

D. Level-order

Correct Answer: C. In-order

Question 7

What is the worst-case search complexity of an unbalanced binary search tree containing n nodes?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 8

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

A. Selection sort

B. Merge sort

C. Quicksort with an extreme pivot

D. Linear search

Correct Answer: B. Merge sort

Question 9

What is the principal advantage of a circular array queue over an array queue that shifts elements after removal?

A. It guarantees sorted elements

B. It provides constant-time indexing of every tree node

C. It can avoid shifting and support constant-time basic operations

D. It prevents all overflow regardless of capacity

Correct Answer: C. It can avoid shifting and support constant-time basic operations

Question 10

If a linked list contains n nodes, what is the time complexity of searching for an arbitrary value?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)