Classifying algorithms

An iterative algorithm repeats with a loop; a recursive algorithm solves a problem by calling itself on a smaller one. Anything recursive can be written iteratively (using your own stack if needed) and vice versa.

Recursion matches self-similar problems (trees, divide and conquer) and costs a stack frame per call. Loops are lighter. Step through the factorial animation to watch the call stack grow and unwind.

1static long factIterative(int n) { long r = 1; for (int i = 2; i <= n; i++) r *= i; return r; }
2static long factRecursive(int n) { return n <= 1 ? 1 : n * factRecursive(n - 1); }

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

A deterministic algorithm follows the same steps for the same input. A randomised algorithm uses random choices, so its running time (Las Vegas: always correct) or even its answer (Monte Carlo: correct with high probability) varies.

Randomised quick sort picks a random pivot so no input is consistently bad. A Bloom filter is Monte Carlo: it may report false positives but never false negatives.

An exact algorithm returns the optimal answer. An approximation returns an answer within a provable factor of optimal when exact solutions are too expensive (many NP-hard problems).

Example: the greedy 2-approximation for vertex cover picks both ends of any uncovered edge and is guaranteed to use at most twice the optimal number of vertices. Chapter 61 covers approximation formally.

An online algorithm must answer as each input item arrives, without seeing the future. An offline algorithm sees all of the input first and can reorder or preprocess it.

The running median is online: after every new number it must report the median so far. Sorting all numbers first is offline. Watch the two-heap solution update after every arrival.

1class MedianFinder {
2    PriorityQueue<Integer> low  = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap
3    PriorityQueue<Integer> high = new PriorityQueue<>();                          // min-heap
4
5    void add(int x) {
6        low.add(x);
7        high.add(low.poll());                 // every low value <= every high value
8        if (high.size() > low.size()) {
9            low.add(high.poll());             // keep low the same size or one larger
10        }
11    }
12
13    double median() {
14        return low.size() > high.size() ? low.peek() : (low.peek() + high.peek()) / 2.0;
15    }
16}

A sequential algorithm does one step at a time. A parallel algorithm splits work across threads or cores. Divide and conquer algorithms such as merge sort parallelise naturally because the two halves are independent.

Parallelism helps only when the work is large enough to pay for the splitting and joining. In Java, Arrays.parallelSort and parallel streams do this for you; measure before trusting them.

1int[] big = new Random(1).ints(5_000_000).toArray();
2Arrays.parallelSort(big);                       // splits, sorts in parallel, merges
3long evens = Arrays.stream(big).parallel().filter(x -> x % 2 == 0).count();

An in-place algorithm uses O(1) extra memory beyond its input (or O(log n) for a recursion stack) and rearranges the input itself: insertion sort, heap sort, quick sort. An out-of-place one needs memory that grows with the input: merge sort's buffer, counting sort's output array.

In-place saves memory but destroys the original order, which matters if the caller still needs the input.