# 1 Introduction

## Notes

• Problem: binary relationship from inputs to outputs

• Algorithm: procedure mapping each input to a single output

• An algorithm solves a problem if it returns a correct output for each and every problem input
• Correctness:

• For small inputs: can use case analysis
• For arbitrarily large inputs: algorithm either is recursive or loop in some way. Use induction.
• Efficiency: how fast does an algorithm produce a correct output?

• Count the number of fixed time operations algorithm takes to return
• Asymptotic Notation: ignore constant factors and low order terms
• Model of Computation: what operations on the machine can be performed in $O\left(1\right)$$O(1)$ time.

• Machine word: block of w bits (w is word size of a w-bit Word-RAM)

• Memory: Addressable sequence of machine words

• Processor supports many constant time operations on a $O\left(1\right)$$O(1)$ number of words (integers):

• integer arithmetic: (+, -, *, //, %)
• logical operators: (&&, ||, !, ==, <, >, <=, =>)
• bitwise arithmetic: (&, |, <<, >>, ...)
• Data Structure : a way to store non-constant data, that supports a set of operations

• A collection of operations is called an interface

• Example:

• Sequence: Extrinsic order to items (first, last, nth)
• Set: Intrinsic order to items (queries based on item keys)
• Data structures may implement the same interface with different performance

• Example: Static Array - fixed width slots, fixed length, static sequence interface

• StaticArray(n): allocate static array of size n initialized to 0 in $\Theta \left(n\right)$$Θ(n)$ time
• StaticArray.get_at(i): return word stored at array index i in $\Theta \left(1\right)$$Θ(1)$ time
• StaticArray.set_at(i, x): write word x to array index i in $\Theta \left(1\right)$$Θ(1)$ time

### More on Asymptotic Notation

• $O$$O$ Notation:

• Non-negative function $g\left(n\right)$$g(n)$ is in $O\left(f\left(n\right)\right)$$O(f(n))$ if and only if there exists a positive real number $c$$c$ and positive integer ${n}_{0}$$n_0$ such that $g\left(n\right)\le c·f\left(n\right)$$g(n) ≤ c · f(n)$ for all $n\ge {n}_{0}$$n ≥ n_0$.
• $\Omega$$Ω$ Notation:

• Non-negative function $g\left(n\right)$$g(n)$ is in $\Omega \left(f\left(n\right)\right)$$Ω(f(n))$ if and only if there exists a positive real number c and positive integer ${n}_{0}$$n_0$ such that $c·f\left(n\right)\le g\left(n\right)$$c · f(n) ≤ g(n)$ for all $n\ge {n}_{0}$$n ≥ n_0$.
• $\Theta Notation$$Θ Notation$:

• Non-negative $g\left(n\right)$$g(n)$ is in $\Theta \left(f\left(n\right)\right)$$Θ(f(n))$ if and only if $g\left(n\right)\in O\left(f\left(n\right)\right)\cap \Omega \left(f\left(n\right)\right)$$g(n) ∈ O(f(n))∩Ω(f(n))$

# 2 Data Structures

## Notes

### Data Structure Interfaces

• A data structure is a way to store data, with algorithms that support operations on the data
• Collection of supported operations is called an interface (also API or ADT)
• Interface is a specification: what operations are supported (the problem!)
• Data structure is a representation: how operations are supported (the solution!)

### Sequence Interface (L02, L07)

• Maintain a sequence of items (order is extrinsic)
• Ex: (${x}_{0}$$x_0$, ${x}_{1}$$x_1$, ${x}_{2}$$x_2$, . . . , ${x}_{n-1}$$x_{n-1}$) (zero indexing)
• (use n to denote the number of items stored in the data structure)
• Supports sequence operations:
• Special case interfaces:

• stack: insert_last(x) and delete_last()
• queue: insert_last(x) and delete_first()

### Set Interface (L03-L08)

• Maintain a set of items having unique keys (e.g., item x has key x.key)

• (Set or multi-set? We restrict to unique keys for now.)

• Often we let key of an item be the item itself, but may want to store more info than just key

• Supports set operations:

• Special case interfaces:

• dictionary: set without the Order operations

### Array Sequence

• Array is great for static operations! get at(i) and set at(i, x) in Θ(1) time!

• But not so great at dynamic operations...

• (For consistency, we maintain the invariant that array is full)

• Then inserting and removing items requires:

• reallocating the array
• shifting all items after the modified item

• Pointer data structure (this is not related to a Python “list”)
• Each item stored in a node which contains a pointer to the next node in sequence
• Each node has two fields: node.item and node.next
• Can manipulate nodes simply by relinking pointers!
• Maintain pointers to the first node in sequence (called the head)
• Can now insert and delete from the front in $\Theta \left(1\right)$$Θ(1)$ time! Yay!
• (Inserting/deleting efficiently from back is also possible; you will do this in PS1)
• But now get_at(i) and set_at(i, x) each take $O\left(n\right)$$O(n)$ time... :(

### Dynamic Array Sequence

• Make an array efficient for last dynamic operations
• Python “list” is a dynamic array
• Idea! Allocate extra space so reallocation does not occur with every dynamic operation
• Fill ratio: $0\le r\le 1$$0 ≤ r ≤ 1$ the ratio of items to space
• Whenever array is full ($r=1$$r = 1$), allocate $\Theta \left(n\right)$$Θ(n)$ extra space at end to fill ratio ${r}_{i}$$r_i$ (e.g., 1/2)
• Will have to insert $\Theta \left(n\right)$$Θ(n)$ items before the next reallocation
• A single operation can take $\Theta \left(n\right)$$Θ(n)$ time for reallocation
• However, any sequence of $\Theta \left(n\right)$$Θ(n)$ operations takes $\Theta \left(n\right)$$Θ(n)$ time
• So each operation takes $\Theta \left(1\right)$$Θ(1)$ time “on average”

### Amortized Analysis

• Data structure analysis technique to distribute cost over many operations
• Operation has amortized cost $T\left(n\right)$$T(n)$ if k operations cost at most $\le kT\left(n\right)$$≤ kT(n)$
• $T\left(n\right)$$T(n)$ amortized” roughly means $T\left(n\right)$$T(n)$ “on average” over many operations
• Inserting into a dynamic array takes $\Theta \left(1\right)$$Θ(1)$ amortized time

### Dynamic Array Deletion

• Delete from back? $\Theta \left(1\right)$$Θ(1)$ time without effort, yay!
• However, can be very wasteful in space. Want size of data structure to stay $\Theta \left(n\right)$$Θ(n)$
• Attempt: if very empty, resize to r = 1. Alternating insertion and deletion could be bad...
• Idea! When $r<{r}_{d}$$r < r_d$, resize array to ratio ${r}_{i}$$r_i$ where ${r}_{d}<{r}_{i}$$r_d < r_i$ (e.g., ${r}_{d}=1/4,{r}_{i}=1/2$$r_d = 1/4, r_i = 1/2$)
• Then $\Theta \left(n\right)$$Θ(n)$ cheap operations must be made before next expensive resize
• Can limit extra space usage to $\left(1+\epsilon \right)n$$(1 + ε)n$ for any $\epsilon >0$$ε > 0$ (set ${r}_{d}=\frac{1}{1+ϵ},{r}_{i}=\frac{{r}_{d}+1}{2}$$r_d = \frac{1}{1+\epsilon}, r_i = \frac{r_d + 1}{2}$)
• Dynamic arrays only support dynamic last operations in $\Theta \left(1\right)$$Θ(1)$ time
• Python List append and pop are amortized $O\left(1\right)$$O(1)$ time, other operations can be $O\left(n\right)$$O(n)$!
• (Inserting/deleting efficiently from front is also possible; you will do this in PS1)

# 3 Sorting

## Notes

### Set Interface

• Storing items in an array in arbitrary order can implement a (not so efficient) set

• Stored items sorted increasing by key allows:

• faster find min/max (at first and last index of array)
• faster finds via binary search: $O\left(logn\right)$$O(log n)$
• But how to construct a sorted array efficiently?

### Sorting

• Given a sorted array, we can leverage binary search to make an efficient set data structure.

• Input: (static) array A of n numbers

• Output: (static) array B which is a sorted permutation of A

• Permutation: array with same elements in a different order
• Sorted: B[i - 1]B[i] for all $i\in 1,...,n$$i ∈ {1, . . . , n}$
• Example: $\left[8,2,4,9,3\right]\to \left[2,3,4,8,9\right]$$[8, 2, 4, 9, 3] → [2, 3, 4, 8, 9]$

• A sort is destructive if it overwrites $A$$A$ (instead of making a new array $B$$B$ that is a sorted version of $A$$A$)

• A sort is in place if it uses $O\left(1\right)$$O(1)$ extra space (implies destructive: in place ⊆ destructive)

#### Permutation Sort

• There are $n!$$n!$ permutations of A, at least one of which is sorted. (Due to duplications)
• For each permutation, check whether sorted in $\Theta \left(n\right)$$Θ(n)$
• Example: $\left[2,3,1\right]\to \left[1,2,3\right],\left[1,3,2\right],\left[2,1,3\right],\left[2,3,1\right],\left[3,1,2\right],\left[3,2,1\right]$$[2, 3, 1] → {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}$
def permutation_sort(A):    """Sort A"""    for B in permutations(A): # O(n!)        if is_sorted(B): # O(n)    return B
• permutation sort analysis:

• Correct by case analysis: try all possibilities (Brute Force)
• Running time: $\Omega \left(n!·n\right)$$Ω(n! · n)$ which is exponential :(

### Solving Recurrences

• Substitution: Guess a solution, replace with representative function, recurrence holds true
• Recurrence Tree: Draw a tree representing the recursive calls and sum computation at nodes
• Master Theorem: A formula to solve many recurrences (R03)

### Selection Sort

• Find a largest number in prefix A[:i + 1] and swap it to A[i]
• Recursively sort prefix A[:i]
• Example: $\left[8,2,4,9,3\right],\left[8,2,4,3,9\right],\left[3,2,4,8,9\right],\left[3,2,4,8,9\right],\left[2,3,4,8,9\right]$$[8, 2, 4, 9, 3], [8, 2, 4, 3, 9], [3, 2, 4, 8, 9], [3, 2, 4, 8, 9], [2, 3, 4, 8, 9]$
xxxxxxxxxxdef selection_sort(A, i=None):    """Sort A[:i+1]"""    if i is None: i = len(A) - 1    if i > 0:        j = prefix_max(A, i)        A[i], A[j] = A[j], A[i]        selection_sort(A, i - 1)        def prefix_max(A, i):    """Return index of maximum in A[:i+1]"""    if i > 0:        j = prefix_max(A, i - 1)        if A[i] < A[j]:            return j    return i
• prefix_max analysis:

• Base case: for i = 0, array has one element, so index of max is $i$$i$

• Induction: assume correct for $i$$i$, maximum is either the maximum of A[:i] or A[i], returns correct index in either case.

• $S\left(1\right)=\Theta \left(1\right);S\left(n\right)=S\left(n-1\right)+\Theta \left(1\right)$$S(1) = Θ(1); S(n) = S(n - 1) + Θ(1)$

• Substitution: $S\left(n\right)=\Theta \left(n\right)$$S(n) = Θ(n)$, $cn=\Theta \left(1\right)+c\left(n-1\right)=⇒1=\Theta \left(1\right)$$cn = Θ(1) + c(n - 1) =⇒ 1 = Θ(1)$
• Recurrence tree: chain of $n$$n$ nodes with $\Theta \left(1\right)$$Θ(1)$ work per node, ${\mathrm{\Sigma }}_{i=0}^{n-1}1=\Theta \left(n\right)$$\Sigma_{i=0}^{n-1}1=Θ(n)$

### Insertion Sort

• Recursively sort prefix A[:i]
• Sort prefix A[:i + 1] assuming that prefix A[:i] is sorted by repeated swaps
• Example: $\left[8,2,4,9,3\right],\left[2,8,4,9,3\right],\left[2,4,8,9,3\right],\left[2,4,8,9,3\right],\left[2,3,4,8,9\right]$$[8, 2, 4, 9, 3], [2, 8, 4, 9, 3], [2, 4, 8, 9, 3], [2, 4, 8, 9, 3], [2, 3, 4, 8, 9]$
xxxxxxxxxxdef insertion_sort(A, i=None):    """Sort A[:i+1]"""    if i is None: i = len(A) - 1    if i > 0:        insertion_sort(A, i-1)        insert_last(A, i)        def insert_last(A, i):    """Sort A[:i+1] assuming sorted A[:i]"""    if i > 0 and A[i] < A[i-1]:        A[i], A[i-1] = A[i-1], A[i]        insert_last(A, i-1)
• insert_last analysis:

• Base case: for $i=0$$i = 0$, array has one element so is sorted
• Induction: assume correct for $i$$i$, if $A\left[i\right]>=A\left[i-1\right]$$A[i] >= A[i - 1]$, array is sorted; otherwise, swapping last two elements allows us to sort A[:i] by induction. □
• $S\left(1\right)=\Theta \left(1\right);S\left(n\right)=S\left(n-1\right)+\Theta \left(1\right)=⇒S\left(n\right)=\Theta \left(n\right)$$S(1) = Θ(1); S(n) = S(n - 1) + Θ(1) =⇒ S(n) = Θ(n)$
• insertion_sort analysis:

• Base case: for $i=0$$i = 0$, array has one element so is sorted
• Induction: assume correct for $i$$i$, algorithm sorts A[:i] by induction, and then insert last correctly sorts the rest as proved above. □
• $T\left(1\right)=\Theta \left(1\right);T\left(n\right)=T\left(n-1\right)+\Theta \left(n\right)=⇒T\left(n\right)=\Theta \left({n}^{2}\right)$$T(1) = Θ(1); T(n) = T(n - 1) + Θ(n) =⇒ T(n) = Θ(n^2)$

### Merge Sort

• Recursively sort first half and second half (may assume power of two)
• Merge sorted halves into one sorted list (two finger algorithm)
• Example: $\left[7,1,5,6,2,4,9,3\right],\left[1,7,5,6,2,4,3,9\right],\left[1,5,6,7,2,3,4,9\right],\left[1,2,3,4,5,6,7,9\right]$$[7, 1, 5, 6, 2, 4, 9, 3], [1, 7, 5, 6, 2, 4, 3, 9], [1, 5, 6, 7, 2, 3, 4, 9], [1, 2, 3, 4, 5, 6, 7, 9]$
xxxxxxxxxxdef merge_sort(A, lo=0, hi=None):    """Sort A[lo:hi]"""    if hi is None: hi = len(A)    if hi - lo > 1:        mid = (lo + hi + 1) // 2        merge_sort(A, lo, mid)        merge_sort(A, mid, hi)        left, right = A[lo:mid], A[mid:hi]        merge(left, right, A, len(left), len(right), lo, hi)        def merge(left, right, A, i, j, lo, hi):    """Merge sorted left[:i] anr right[:j] into A[lo:hi]"""    if lo < hi:        if (j <= 0) or (i > 0 and left[i-1] > right[j-1]):            A[hi-1] = left[i-1]            i -= 1        else:            A[hi-1] = right[j-1]            j -= 1        merge(left, right, A, i, j, lo, hi -1)
• merge analysis:

• Base case: for $n=0$$n = 0$, arrays are empty, so vacuously correct
• Induction: assume correct for $n$$n$, item in A[r] must be a largest number from remaining prefixes of left and right, and since they are sorted, taking largest of last items suffices; remainder is merged by induction. □
• $S\left(0\right)=\Theta \left(1\right);S\left(n\right)=S\left(n-1\right)+\Theta \left(1\right)=⇒S\left(n\right)=\Theta \left(n\right)$$S(0) = Θ(1); S(n) = S(n - 1) + Θ(1) =⇒ S(n) = Θ(n)$
• merge_sort analysis:

• Base case: for $n=1$$n = 1$, array has one element so is sorted

• Induction: assume correct for $k$k < n$, algorithm sorts smaller halves by induction, and then merge merges into a sorted array as proved above. □

• $T\left(1\right)=\Theta \left(1\right);T\left(n\right)=2T\left(n/2\right)+\Theta \left(n\right)$$T(1) = Θ(1); T(n) = 2T(n/2) + Θ(n)$

• Substitution: Guess $T\left(n\right)=\Theta \left(nlogn\right)$$T(n) = Θ(n log n)$

$cnlogn=\Theta \left(n\right)+2c\left(n/2\right)log\left(n/2\right)=⇒cnlog\left(2\right)=\Theta \left(n\right)$$cn log n = Θ(n) + 2c(n/2)log(n/2) =⇒ cn log(2) = Θ(n)$

• Recurrence Tree: complete binary tree with depth $log2n$$log2 n$ and $n$$n$ leaves, level $i$$i$ has ${2}^{i}$$2^i$ nodes with $O\left(n/{2}^{i}\right)$$O(n/2^i )$ work each, total: ${\mathrm{\Sigma }}_{i=0}^{lo{g}_{2}^{n}}\left(2i\right)\left(n/{2}^{i}\right)={\mathrm{\Sigma }}_{i=0}^{lo{g}_{2}^{n}}n=\Theta \left(nlogn\right)$$\Sigma_{i=0}^{log_2^n}(2i )(n/2^i ) = \Sigma_{i=0}^{log_2^n}n = Θ(n log n)$

### Master Theorem

• The Master Theorem provides a way to solve recurrence relations in which recursive calls decrease problem size by a constant factor.
• Given a recurrence relation of the form $T\left(n\right)=aT\left(n/b\right)+f\left(n\right)$$T(n) = aT(n/b)+ f(n)$ and $T\left(1\right)=\Theta \left(1\right)$$T(1) = Θ(1)$, with branching factor $a\ge 1$$a ≥ 1$, problem size reduction factor $b>1$$b > 1$, and asymptotically non-negative function $f\left(n\right)$$f(n)$, the Master Theorem gives the solution to the recurrence by comparing $f\left(n\right)$$f(n)$ to ${a}^{lo{g}_{b}^{n}}={n}^{lo{g}_{b}^{a}}$$a^{log_b^{n}}=n^{log_b^a}$ , the number of leaves at the bottom of the recursion tree.
• When $f\left(n\right)$$f(n)$ grows asymptotically faster than $n$$n$ , the work done at each level decreases geometrically so the work at the root dominates;
• alternatively, when $f\left(n\right)$$f(n)$ grows slower, the work done at each level increases geometrically and the work at the leaves dominates.
• When their growth rates are comparable, the work is evenly spread over the tree’s $O\left(logn\right)$$O(log n)$ levels. • The Master Theorem takes on a simpler form when f(n) is a polynomial, such that the recurrence has the from $T\left(n\right)=aT\left(n/b\right)+\Theta \left({n}^{c}\right)$$T(n) = aT(n/b) + Θ(n^c )$ for some constant $c\ge 0$$c ≥ 0$.
• This special case is straight-forward to prove by substitution (this can be done in recitation).
• To apply the Master Theorem (or this simpler special case), you should state which case applies, and show that your recurrence relation satisfies all conditions required by the relevant case.
• There are even stronger (more general) formulas to solve recurrences, but we will not use them in this class.

# 4 Hashing

## Notes

### Comparison Model

• In this model, assume algorithm can only differentiate items via comparisons
• Comparable items: black boxes only supporting comparisons between pairs
• Comparisons are $<,\le ,>,\ge ,=,\ne$$<, ≤, >, ≥, =, \neq$, outputs are binary: True or False
• Goal: Store a set of n comparable items, support find(k) operation
• Running time is lower bounded by # comparisons performed, so count comparisons!

### Decision Tree

• Any algorithm can be viewed as a decision tree of operations performed
• An internal node represents a binary comparison, branching either True or False
• For a comparison algorithm, the decision tree is binary (draw example)
• A leaf represents algorithm termination, resulting in an algorithm output
• A root-to-leaf path represents an execution of the algorithm on some input
• Need at least one leaf for each algorithm output, so search requires $\ge n+1$$≥ n + 1$ leaves

### Comparison Search Lower Bound

• What is worst-case running time of a comparison search algorithm?
• running time $\ge$$≥$ # comparisons $\ge$$≥$ max length of any root-to-leaf path $\ge$$≥$ height of tree
• What is minimum height of any binary tree on $\ge n$$≥ n$ nodes?
• Minimum height when binary tree is complete (all rows full except last)
• $Height\ge ⌈lg\left(n+1\right)⌉-1=\Omega \left(logn\right)$$Height ≥ \lceil lg(n + 1) \rceil - 1 = Ω(log n)$, so running time of any comparison sort is $\Omega \left(logn\right)$$Ω(log n)$S
• Sorted arrays achieve this bound! Yay!
• More generally, height of tree with $\Theta \left(n\right)$$Θ(n)$ leaves and max branching factor $b$$b$ is $\Omega \left(logbn\right)$$Ω(logb n)$
• To get faster, need an operation that allows super-constant $\omega \left(1\right)$$ω(1)$ branching factor. How??

### Direct Access Array

• Exploit Word-RAM $O\left(1\right)$$O(1)$ time random access indexing! Linear branching factor!
• Idea! Give item unique integer key k in $\left\{0,...,u-1\right\}$$\{0, . . . , u - 1\}$, store item in an array at index $k$$k$
• Associate a meaning with each index of array.
• If keys fit in a machine word, i.e. $u\le {2}^{w}$$u ≤ 2^w$, worst-case $O\left(1\right)$$O(1)$ find/dynamic operations! Yay!
• 6.006: assume input numbers/strings fit in a word, unless length explicitly parameterized
• Anything in computer memory is a binary integer, or use (static) 64-bit address in memory
• But space $O\left(u\right)$$O(u)$, so really bad if $n\ll u$$n \ll u$... :(
• Example: if keys are ten-letter names, for one bit per name, requires ${26}^{10}\approx 17.6$$26^{10} ≈ 17.6$ TB space
• How can we use less space?

### Hashing

• Idea! If $n\ll u$$n \ll u$, map keys to a smaller range $m=\Theta \left(n\right)$$m = Θ(n)$ and use smaller direct access array

• Hash function: $h\left(k\right):\left\{0,...,u-1\right\}\to \left\{0,...,m-1\right\}$$h(k) : \{0, . . . , u - 1\} → \{0, . . . , m - 1\}$ (also hash map)

• Direct access array called hash table, $h\left(k\right)$$h(k)$ called the hash of key k

• If $m\ll u$$m \ll u$, no hash function is injective by pigeonhole principle

• Always exists keys $a,b$$a, b$ such that $h\left(a\right)=h\left(b\right)$$h(a) = h(b)$ $\to$$→$ Collision! :(

• Can’t store both items at same index, so where to store? Either:

• store somewhere else in the array (open addressing)

• complicated analysis, but common and practical
• store in another data structure supporting dynamic set interface (chaining)

### Chaining

• Idea! Store collisions in another data structure (a chain)
• If keys roughly evenly distributed over indices, chain size is $n/m=n/\Omega \left(n\right)=O\left(1\right)!$$n/m = n/Ω(n) = O(1)!$
• If chain has $O\left(1\right)$$O(1)$ size, all operations take $O\left(1\right)$$O(1)$ time! Yay!
• If not, many items may map to same location, e.g. $h\left(k\right)=constant$$h(k) = constant$, chain size is $\Theta \left(n\right)$$Θ(n)$ :(
• Need good hash function! So what’s a good hash function?

### Hash Functions

#### Division (bad): $h(k) = k \ \mod \ m$

• Heuristic, good when keys are uniformly distributed!
• $m$$m$ should avoid symmetries of the stored keys
• Large primes far from powers of 2 and 10 can be reasonable
• Python uses a version of this with some additional mixing
• If $u\ll n$$u \ll n$, every hash function will have some input set that will a create $O\left(n\right)$$O(n)$ size chain
• Idea! Don’t use a fixed hash function! Choose one randomly (but carefully)!

#### Universal (good, theoretically): $h_{ab}{(k)}=(((ak+b) \mod \ p) \mod \ m)$

• Hash Family $\mathcal{H}\left(p,m\right)=\left\{{h}_{ab}|a,b\in \left\{0,...,p-1\right\}anda\ne 0\right\}$$\mathcal{H}(p,m) = \{h_{ab}| a,b \in \{0,...,p-1\} and a \neq 0 \}$
• Parameterized by a fixed prime $p>u$$p > u$, with $a$$a$ and $b$$b$ chosen from range $\left\{0,...,p-1\right\}$$\{0,...,p-1\}$
• $\mathcal{H}$$\mathcal{H}$ is a Universal family: $\underset{h\in \mathcal{H}}{Pr}\left\{h\left({k}_{i}\right)=h\left({k}_{j}\right)\right\}\le 1/m\phantom{\rule{2em}{0ex}}\mathrm{\forall }{k}_{i}\ne {k}_{j}\in \left\{0,...,u-1\right\}$$\underset{h\in\mathcal{H}}{Pr}\{h(k_i) = h(k_j)\} \leq 1/m \qquad \forall k_i \neq k_j \in \{0,...,u-1\}$
• Why is universality useful? Implies short chain lengths! (in expectation)
• ${X}_{ij}$$X_{ij}$ indicator random variable over $h \in \mathcal{H}: \ X_{ij}=1 \ if \ h(k_i) = h(k_j), X_{ij} = 0 \ otherwise$
• Size of chain at index $h\left({k}_{i}\right)$$h(k_i)$ is random variable ${X}_{i}={\mathrm{\Sigma }}_{j}{X}_{ij}$$X_i = \Sigma_{j}{X_{ij}}$
• Expected size of chain at index $h\left({k}_{i}\right)$$h(k_i)$:

$\begin{array}{rl}\underset{h\in \mathcal{H}}{\mathbb{E}}{X}_{i}=\underset{h\in \mathcal{H}}{\mathbb{E}}\left\{{\mathrm{\Sigma }}_{j}{X}_{ij}\right\}={\mathrm{\Sigma }}_{j}\underset{h\in \mathcal{H}}{\mathbb{E}}{X}_{ij}& =1+{\mathrm{\Sigma }}_{j\ne i}\underset{h\in \mathcal{H}}{\mathbb{E}}{X}_{ij}\\ & =1+{\mathrm{\Sigma }}_{j\ne i}\left(1\right)\underset{h\in \mathcal{H}}{Pr}\left\{h\left({k}_{i}\right)=h\left({k}_{j}\right)\right\}+\left(0\right)\underset{h\in \mathcal{H}}{Pr}\left\{h\left({k}_{i}\right)\ne h\left({k}_{j}\right)\right\}\\ & \le 1+{\mathrm{\Sigma }}_{j\ne i}1/m=1+\left(n-1\right)/m\end{array}$\begin{align}\underset{h\in\mathcal{H}}{\mathbb{E}}{X_i} = \underset{h\in\mathcal{H}}{\mathbb{E}} \{\Sigma_{j}{X_{ij}}\} = \Sigma_{j}\underset{h\in\mathcal{H}}{\mathbb{E}}{X_{ij}} & = 1 + \Sigma_{j\neq i}\underset{h\in\mathcal{H}}{\mathbb{E}}{X_{ij}}\\ &= 1 + \Sigma_{j\neq i}(1)\underset{h\in\mathcal{H}}{Pr}\{h(k_i) = h(k_j)\} + (0)\underset{h\in\mathcal{H}}{Pr}\{h(k_i) \neq h(k_j)\}\\ &\leq 1 + \Sigma_{j\neq i} 1/m = 1 + (n-1) /m\end{align}

• Since $m=\Omega \left(n\right)$$m = Ω(n)$, load factor $\alpha =n/m=O\left(1\right)$$α = n/m = O(1)$, so $O\left(1\right)$$O(1)$ in expectation!

#### Dynamic

• If $n/m$$n/m$ far from 1, rebuild with new randomly chosen hash function for new size m
• Same analysis as dynamic arrays, cost can be amortized over many dynamic operations
• So a hash table can implement dynamic set operations in expected amortized O(1) time! :)