Algorithms Review

Sorting problem

Input: a list of n numbers. Output: the numbers arranged in increasing order.

Insertion sort (definition)

In-place sort that grows a sorted section on the left, inserting each next element into its proper place by comparing right-to-left and swapping/shifting larger elements right (like sorting a hand of cards).

In-place sorting

The algorithm sorts using the original array; when it terminates the numbers are sorted in that same array (e.g., insertion sort).

Merge sort (definition)

Divide-and-conquer sort: Divide the array into two halves of size n/2; Conquer by recursively merge-sorting each half; Combine by merging the two sorted halves into one sorted array.

Merge step of merge sort (definition and runtime)

Copies the two sorted halves into L[] and R[] (each ending with an infinity sentinel), then repeatedly compares the front elements and places the smaller into A. One comparison per element moved, so Θ(n).

Merge sort base case

An array of size 1 is already sorted, so MergeSort returns immediately (takes constant time c1).

Heap sort (definition)

Build a max-heap (BottomBuildHeap), then for i = n down to 2 call Delete-Max. Each deleted max is swapped to the end of the array, so the array ends up sorted.

Comparison-based sorting algorithm

A sorting algorithm that uses only comparisons between pairs of elements to determine the sorted order (e.g., insertion sort, merge sort, heap sort).

Decision tree (for sorting)

A binary tree where each internal node is a yes/no comparison (e.g., Is A ≤ B?). Leaves are possible outcomes (sorted orders); the path length from root to leaf = number of comparisons; worst case = height of the tree.

Height of a decision tree / binary tree with L leaves

At least log2(L). A decision tree with n possible outcomes needs at least log2(n) questions in the worst case.

Sorting decision tree: number of leaves

At least n! leaves (one per possible sorted order), so the height is at least log2(n!), which is Ω(n log n).

Comparison sort lower bound (Theorem)

Any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case. Hence merge sort and heap sort (Θ(n log n)) are optimal among comparison sorts.

Why can counting/radix/bucket sort beat Ω(n log n)?

They are not comparison-based; they make assumptions about the input (e.g., bounded integers, digits, uniform distribution) and use extra storage.

Counting sort (definition)

Assumes n integers each between 0 and k. Uses an extra array C[0..k]. Step 1: count occurrences of each value in C. Step 2: make C[i] = number of elements ≤ i (C[i] = C[i] + C[i-1]). Step 3: go through A from the back, place each A[i] at position C[A[i]] in the output, and decrement C[A[i]].

Stable sort

A sort that keeps duplicate elements in the same relative order in the output as in the input. Counting sort is stable (it processes A from back to front).

Radix sort (definition)

Assumes each number has at most d digits and each digit takes one of r values. Sorts one digit at a time starting with the least significant digit, using counting sort (a stable sort) for each pass.

Why does radix sort work?

Counting sort is stable, so sorting by a later (more significant) digit does not disrupt the order established by earlier digits. Example: 426 and 432 share the leading digit 4, so they stay in the order 426, 432.

Radix sort example: values less than 1000

Each number has at most 3 digits so d = 3; decimal digits have 10 possibilities so r = 10. Three counting-sort passes (ones, tens, hundreds).

Bucket sort (definition)

Create empty buckets, each covering a range of values. 1) Put each number in its bucket - O(n). 2) Sort each bucket with insertion sort (or another comparison sort) - sum of O(n_i^2). 3) Concatenate the buckets in order - O(n). Works on real numbers, not just integers.

Bucket sort (assumption)

The input is uniformly distributed over some range a ≤ x ≤ b (numbers may be real).

Bucket sort: why is the expected time Θ(n)?

With n buckets and uniform data, each bucket expects about 1 item. The bucket size n_i is a binomial random variable with constant expected value, so n_i^2 is also expected to be constant. Thus the sum of O(n_i^2) over all buckets is O(n); distributing and outputting are each Θ(n).

Uniformly distributed numbers

Numbers over a range a ≤ x ≤ b that are equally likely to fall into any bucket of equal size (b - a)/k.

Randomized-Select (definition)

Divide-and-conquer selection (like Quicksort): pick a random pivot p, partition into smaller/larger elements, find the pivot's rank r. If r = k return p; if k < r recurse on the left part; if k > r recurse on the right part looking for rank k - r.

Randomized-Select (runtime)

Expected Θ(n)/O(n); worst case Θ(n^2) when the pivot is always the max (recurrence T(n) = T(n-1) + cn). The partition step takes Θ(n).

Randomized-Select: good pivot

A pivot from the middle 50% of the (conceptually sorted) elements. The probability is 1/2, so we expect 2 tries per good pivot, and a good pivot leaves at most 3n/4 elements for the recursive call.

Select algorithm (median of medians) - steps

1) Divide n elements into ⌈n/5⌉ groups of 5 - Θ(n). 2) Sort each group and find its median - Θ(n). 3) Recursively find the median of the medians, x - T(n/5). 4) Partition around x and find its rank r - Θ(n). 5) Compare r to k: if r = k return x; if r < k recurse on the larger elements with rank k - r; if r > k recurse on the smaller elements - at most T(3n/4).

Select algorithm (runtime)

O(n) worst case. Recurrence: T(n) = T(n/5) + T(3n/4) + Θ(n), solved by substitution to give T(n) ≤ dn.

Select: why is the recursive call on at most 3n/4 elements?

Elements known to be smaller than x: at least 3 per column in about n/10 columns, so at least 3n/10 ≥ n/4 elements. So the recursive call is on at most 3n/4 elements.

kth order statistic / element of rank k

The kth smallest element of a set. Example: in {3, 15, 10, 4, 6, 7, 1} the element of rank 3 is 4. The median is the order statistic in the middle position.

Finding the minimum (or maximum) of n elements

Takes exactly n - 1 comparisons, which is optimal; runtime O(n).

Insertion sort: best, average, worst runtime and space

Best: Θ(n) (already sorted; inner loop breaks after one comparison per element). Average: Θ(n^2). Worst: Θ(n^2) (reverse-sorted input). Space: O(1) extra (in-place).

Insertion sort: worst-case operation count

Reverse-sorted input: 1+2+…+(n-1) = n(n-1)/2 = n^2/2 - n/2 comparisons, the same number of swaps, and the same number of loop operations, giving an^2 + bn + c = Θ(n^2).

Merge sort: best, average, worst runtime and space

Best: Θ(n log n). Average: Θ(n log n). Worst: Θ(n log n) (T(n) = 2T(n/2) + cn). Space: O(n) extra (Merge copies the halves into L[] and R[]); not in-place.

Heap sort: best, average, worst runtime and space

Best: O(n log n) (Θ(n log n) for distinct keys; only linear if all keys are equal). Average: Θ(n log n). Worst: O(n log n) (BuildHeap O(n) + n Delete-Max calls at O(log n) each). Space: O(1) extra (in-place; the sorted part grows at the end of the array).

Counting sort: best, average, worst runtime and space

Best, average and worst: Θ(n + k) (same for every input; k = largest integer). Space: O(n + k) (count array C[0..k] plus an output array of size n). Stable, not comparison-based.

Counting sort: runtime breakdown

Step 1 (count occurrences) O(n) + Step 2 (prefix sums over C) O(k) + Step 3 (place elements into output, back to front) O(n) = O(n + k). If k is a multiple of n, it is O(n).

Radix sort: best, average, worst runtime and space

Best, average and worst: Θ(d(n + r)) (d passes of counting sort; linear if d and r are constants). Space: O(n + r) (counting array of size O(r) plus an output array of size n). Stable.

Radix sort: runtime breakdown

Each counting-sort pass costs O(n + r) and there are exactly d passes (one per digit), so the total is O(d(n + r)).

Bucket sort: best, average, worst runtime and space

Best: Θ(n) (items spread evenly across buckets). Average (expected): Θ(n) for uniformly distributed data with n equal-size buckets. Worst: O(n^2) (all items land in one bucket and insertion sort is used). Space: O(n) extra (buckets holding the n items plus the bucket array).

Bucket sort: runtime breakdown

Distribute into buckets Θ(n) + sort each bucket with insertion sort (sum of O(n_i^2), expected O(n)) + output the buckets in order Θ(n).

Which sorting algorithms are in-place (O(1) extra space)?

Insertion sort and heap sort.

Which sorting algorithms need extra space?

Merge sort O(n); counting sort O(n + k); radix sort O(n + r); bucket sort O(n).

Which sorting algorithms have the same runtime on every input?

Merge sort Θ(n log n), counting sort Θ(n + k), and radix sort Θ(d(n + r)). (Heap sort is Θ(n log n) for distinct keys.)

Which sorting algorithms have a Θ(n^2) worst case?

Insertion sort (reverse-sorted input) and bucket sort (all elements in one bucket). Merge sort and heap sort are O(n log n) in the worst case.

Which sorting algorithms run in linear time (and under what assumptions)?

Counting sort (integers in 0..k, k = O(n)), radix sort (d digits with r values each, d and r constant), and bucket sort (uniformly distributed input, expected time).

Sorting algorithm summary: runtimes (best / average / worst)

Insertion: n / n^2 / n^2. Merge: n log n / n log n / n log n. Heap: n log n / n log n / n log n. Counting: n+k for all cases. Radix: d(n+r) for all cases. Bucket: n / n (expected, uniform input) / n^2.

Sorting algorithm summary: extra space

Insertion O(1); Merge O(n); Heap O(1); Counting O(n + k); Radix O(n + r); Bucket O(n).

Binary heap

A data structure visualized as a complete binary tree (all levels full except possibly the last, which is filled left to right), stored in an array, satisfying the max-heap (or min-heap) property.

Max-heap property

Every node has a value greater than or equal to all values in its subtree.

Height of a heap

Number of edges on the longest simple path from the root to a leaf. For n nodes it is ⌊log2 n⌋ = Θ(log n). Example: n = 10 gives ⌊log2 10⌋ = 3.

Array implementation of a heap (indices)

Root is A[1]; parent of node i is A[⌊i/2⌋]; left child is A[2i]; right child is A[2i+1]. A.heapsize says how many array elements are currently in the heap.

Bubble-up(A, i)

Swaps the element at index i with its parent whenever it is larger, continuing up toward the root. Restores the heap property for indices 1..i. Runtime O(log n).

Bubble-down(A, i)

Assumes both children of i are valid heaps. Swaps the element at i with its larger child while a child is larger, continuing down the tree. Runtime O(h) for a node of height h, so O(log n) worst case.

Iterative (bubble-up) BuildHeap

Inserts elements one at a time as leaves and bubbles each up. Each insertion is O(log n), so the total is O(n log n).

Bottom-up BuildHeap (BottomBuildHeap)

For j = ⌊n/2⌋ down to 1 call Bubble-down(A, j). Starts at the last internal node (index ⌊n/2⌋). Runtime O(n).

Why is bottom-up BuildHeap O(n)?

At most n/2^h nodes have height h and each costs O(h) = at most ch. T(n) ≤ sum over h of ch·n/2^h ≤ cn · sum of h(1/2)^h = cn(2) = O(n), since most nodes are near the bottom.

Delete-Max (heap)

Swap A[1] with the last heap element, decrease A.heapsize by 1, then Bubble-down(A, 1). Runtime O(log n). The max ends up in the last array position.

Heap operation runtimes

Find max: O(1). Delete max: O(log n). Insert (bubble-up): O(log n). Build heap: O(n) bottom-up, O(n log n) iterative.

Hash table

Table T of size m (much smaller than the universe U) with a hash function h(k) mapping each key k to a position in {0, …, m-1}. Search, insert and delete take O(1) without collisions.

Direct-address table

Array T of size m used when keys come from {0, …, m-1}; key k is stored at T(k). Search, insert, delete are all O(1), but the table must have size m, which can waste a lot of space.

Universe (U) vs keys (hashing)

The universe U is all possible keys (e.g., all 6-digit PINs); the keys are the items actually stored (e.g., the 500 PINs of bank members).

Collision (hashing)

Two different keys hash to the same table position.

Hashing with chaining

Keys that collide are linked together in a linked list at that table slot. Insert: O(1). Search and delete: O(n) worst case (one long chain).

Load factor α

α = n/m (number of keys / table size) = average chain length under uniform hashing. Example: n = 10, m = 5 gives α = 2.

Uniform hash function

A hash function that is equally likely to hash a key to any of the m slots. Expected chain length is α = n/m.

Hashing with chaining under uniform hashing: runtime

Insert O(1); search O(α + 1); delete O(α + 1). If α is constant, all operations are O(1).

Open addressing

No chains: on a collision, probe other slots following the key's probe sequence until a free slot is found. Requires n ≤ m, so α ≤ 1.

Probe sequence

The order in which slots are tried for a key: a permutation of all table slots, denoted h(k, i) where i is the probe attempt. Example: h(25) = {4, 3, 0, 2, 1} means try slot 4, then 3, then 0, …

Open addressing: deletion problem

Simply emptying a slot can break later searches (a search hits the empty slot and wrongly concludes the key is absent). Using a 'keep looking' marker works but fills the table with markers and becomes inefficient.

Linear probing

Probe h(k), then the next positions in order (wrapping around to the top). Drawback: creates clusters of occupied slots that slow down searches.

Quadratic probing

h(k, i) = h(k) + ai + bi^2 mod m for constants a and b. Example: h(k) = k mod 5, a = b = 1, k = 12: h(12,0) = 2, h(12,1) = 12+1+1 mod 5 = 4, h(12,2) = 12+2+4 mod 5 = 3.

Double hashing

Uses two hash functions: h1(k) gives the first slot and h2(k) gives the offset between probes. Example: h1(25) = 3, h2(25) = 2 gives probe order 3, 5, 7, … (wrapping around).

Open addressing expected probes (Theorem)

For uniform hashing with α < 1, the expected number of probes in a search is at most 1/(1 - α) (worst case is an unsuccessful search).

Open addressing example: expected probes when keys = half the table

m = 2n so α = 1/2. Expected probes = 1/(1 - 1/2) = 2.

Hash example: h(k) = k mod 5

h(1234) = 4, h(3245) = 0, h(1456) = 1 (so these keys go in slots 4, 0, and 1).

Hash example: first letter of last name, table positions 1-26

McDonald goes in position 13, Jamieson in 10, Everest in 5. Drawbacks: wasted space (unused letters) and collisions (same first letter).

Array and linked list operation costs

Sorted array: search O(log n), insert O(n), delete O(n). Unsorted array: search O(n), insert O(n), delete O(n). Sorted list: O(n) for all. Unsorted list: search O(n), insert O(1), delete O(n).

Asymptotic behaviour

How a function (e.g., a running time) grows as n → infinity. Ignores constant factors and lower-order terms, so it is independent of hardware and software.

RAM model

Random-access machine: instructions run one after another, and elementary operations (arithmetic, comparison, memory load/store/swap, function call/return) each take constant time (one 'step').

Running time of an algorithm

The number of elementary steps the algorithm takes, expressed as a function of the input size n.

Worst-case running time

The number of steps in the worst possible input of size n; gives an upper bound on the runtime.

Big-O definition

f(n) is O(g(n)) if there are constants C and k such that f(n) ≤ C·g(n) for all n > k (upper bound).

Big-Omega definition

f(n) is Ω(g(n)) if there is a constant C such that f(n) ≥ C·g(n) for all n > k (lower bound).

Big-Theta definition

f(n) is Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)); an asymptotically tight bound (f is sandwiched between multiples of g).

Order of growth (slowest to fastest)

log n < (log n)^2 < (log n)^3 < … < n^c (0<c<1) < n < n log n < n^2 < n^3 < … < 2^n < 3^n < … < n!

Log inequality used in big-O proofs

log2 n ≤ n for all n ≥ 1. More generally, for b > 1 and any a > 0, log_b n ≤ n^a for large enough n. The log base is omitted in big-O (changing base only changes a constant).

Big-O example: n^2 + 3n + 1

n^2 + 3n + 1 ≤ n^2 + 3n^2 + n^2 = 5n^2 for n ≥ 1, so it is O(n^2) with C = 5, k = 1.

Big-O example: 2√n + 5n

Since √n ≤ n for n ≥ 1, f(n) ≤ 2n + 5n = 7n, so f is O(n) with C = 7.

Big-O example: 7n + log n

Using log n ≤ n: f(n) ≤ 8n, so f is O(n) (it is also O(n^2), but O(n) is tighter).

Big-O example: n^4 is not O(n^3)

If n^4 ≤ C·n^3 then n ≤ C for all n > k, which is impossible since n can be arbitrarily large.

Big-O example: n! is O(n^n)

n! = 1·2·3···n ≤ n·n·n···n = n^n for n ≥ 1.

Big-Theta example: n^3 + 1 + log n

Upper: ≤ n^3 + n^3 + n^3 = 3n^3 for n ≥ 1. Lower: ≥ n^3. So it is Θ(n^3).

Big-Theta example: n^2 log n + 2^n

2^n dominates (for n ≥ 7, n^2 log n ≤ 2^n), so 2^n ≤ f(n) ≤ 2·2^n, so f(n) is Θ(2^n).

Recurrence (recursive equation)

An equation that gives a recursive algorithm's running time T(n) in terms of T on smaller inputs. Example (merge sort): T(n) = 2T(n/2) + cn, T(1) = c1.

Recurrence example: Select algorithm

T(n) = T(n/5) + T(3n/4) + Θ(n), solved by substitution: T(n) is O(n).

Recurrence example: Randomized-Select worst case

T(n) = T(n-1) + cn, which solves to Θ(n^2).

Three methods to solve a recurrence

1) Recursion tree. 2) Substitution (guess a solution and prove it by induction). 3) Master method.

Recursion tree method (definition)

Draw the recurrence as a tree: each node holds the non-recursive cost (e.g., the merge cost) and its children hold the recursive subproblems. Sum the cost of each level, then sum over all levels. Works well when a pattern in the per-level cost is easy to spot.

Recursion tree example: T(n) = 2T(n/2) + cn

Level costs: cn, 2(cn/2) = cn, 4(cn/4) = cn, … Every level costs cn and there are log2 n levels, so T(n) = cn log2 n, which is Θ(n log n).

Substitution method: definition

Guess the form of the solution, then prove it is correct by induction (substitute the inductive assumption into the recurrence and show the bound still holds).