Algorithms and complexity

Learning outcomes

Use stepwise refinement, separate input size from running time, and justify a simple time or space bound.

2.1 Algorithms and invariants

An algorithm is a finite, precisely specified procedure for solving a problem. State its inputs, outputs and preconditions. A useful design sequence is: solve a small example by hand, express the steps, refine each vague step, and test boundary cases.

To find the largest of n values, begin with the first value, compare each remaining value with the current maximum, and replace the maximum when necessary. The precondition is n > 0. The loop invariant is: after processing the first i values, the stored maximum is the largest among those i values. Initialisation, maintenance and termination together explain correctness.

2.2 Count the dominant work

Let n be the number of elements. A full traversal performs n visits. Comparing every unordered pair performs n(n − 1)/2 comparisons. Repeatedly halving a search interval takes a number of steps proportional to log₂ n.

A bound describes growth, not seconds. Two Θ(n) algorithms may have different constants, cache behaviour or allocation costs. Benchmarking measures a particular implementation and environment; asymptotic analysis explains how cost grows.

2.3 Big O is not the same as worst case

T(n) ∈ O(f(n)) states an asymptotic upper bound: for sufficiently large n, T(n) ≤ c f(n) for some constant c. Ω gives a lower bound and Θ a tight bound. Best, average and worst case describe which inputs of a size are considered. Each case may have its own bound.

For linear search, a successful match in the first position takes Θ(1) time. A missing value requires Θ(n) time. An average-case claim needs an input model; under a uniform distribution of successful positions, the average number of checks is (n + 1)/2.

Writing O(n²) for a linear traversal is technically an upper bound but uninformative. Prefer the tight bound when known. Also state whether “space” means total storage or auxiliary space, the additional workspace beyond the input and output.

2.4 Worked pair-counting example

An inversion is a pair (i, j) for which i < j and a[i] > a[j]. For {8, 4, 2, 1}, the pairs are (8,4), (8,2), (8,1), (4,2), (4,1), (2,1): six inversions.

count = 0
for i = 0 through n − 1:
    for j = i + 1 through n − 1:
        if a[i] > a[j]:
            count = count + 1
return count

The count of comparisons is 3 + 2 + 1 = 6 for n = 4, and n(n − 1)/2 generally. Time is Θ(n²); auxiliary space is Θ(1), assuming a counter wide enough for the result. Equal values are not inversions. A merge-sort-based method can count inversions in Θ(n log n), but it requires a different algorithm and extra workspace.

2.5 Choose a structure by the workload

An array gives constant-time indexed access but may require shifting on insertion. A linked list permits constant-time relinking when the relevant node or predecessor is already known, but finding a position may take linear time. A balanced search tree supports ordered lookup and update in logarithmic time. A hash table targets key lookup rather than sorted traversal.

Ask: which operations dominate, must order be preserved, how large can the collection become, and what memory constraints apply? “Fastest data structure” has no meaning without that workload.

Practice

1. How many comparisons are made by the inversion algorithm for n = 6?
2. Give the best and worst cases for linear search.
3. A loop repeatedly sets n = n / 2 while n is positive. Explain its asymptotic iteration count.
4. Explain why constant-time insertion into a linked list does not imply constant-time insertion at a numbered position.