CS240 Course Notes

Professor: Arne Storjohann | Term: Fall 2024

Module 1

Much of Computer Science is problem solving: Write a program that converts the given input to the expected output.

When first learning to program, we emphasize correctness. With this course, we will also be concerned with efficiency. We will study efficient methods of storing, accessing, and organizing large collections of data.

Typical operations include: Inserting new data items, deleting data items, searching for specific data items, sorting.

We consider various abstract data types (ADTs), and how to realize them efficiently using appropriate data structures. There is a strong emphasis on mathematical analysis in this course.

Useful Logarithms facts:

• $y={\log }_b(x)$ means $b^y=x$
• $\log (x)$ in this course means ${\log }_2(x)$
• $\log (x\cdot y)=\log (x)+\log (y)$, $\log (x^y)=y\log (x)$, $\log (x)\le x$
• ${\log }_b(a)=\frac{{\log }_{c}a}{{\log }_{c}b}=\frac{1}{{\log }_a(b)}$, $a^{{\log }_{b}c}=c^{{\log }_{b}a}$
• $\log (n!)=\log n+\log (n-1)+\cdots +\log 2+\log 1\in \Theta (n\log n)$

Useful Sums:

• ${\sum }_{i=0}^{n-1}i=\frac{(n-1)n}{2}$
• ${\sum }_{i=0}^{n-1}(a+di)=na+\frac{dn(n-1)}{2}\in \Theta (n^2)$ if $d\ne 0$.

Geometric Sequences:

$$\begin{array}{rl}\sum _{i=0}^{n-1}{2}^i& =2^n-1\\ \sum _{i=0}^{n-1}a{r}^i& =\{\begin{array}{ll}a\frac{r^n-1}{r-1}\in \Theta (r^{n-1})& \text{if }r>1\\ na\in \Theta (n)& \text{if }r=1\\ a\frac{1-r^n}{1-r}\in \Theta (1)& \text{if }0<r<1\end{array}\end{array}$$

Harmonic Sequence:

• $H_n:-{\sum }_{i=1}^n\frac{1}{i}=\ln n+\gamma +o(1)\in \Theta (\log n)$

Algorithms and Problems

Problem: Description of possible input and desired output.

Problem Instance: One possible input for the specified problem.

Algorithm: Step-by-step process for carrying out a series of computations, given an arbitrary instance $I$.

Solving a problem: An algorithm $A$ solves a problem $\Pi$ if, for every instance $I$ of $\Pi$, $A$ computes a valid output for the instance $I$ in finite time.

Program: A program is an implementation of an algorithm using a specified computer language.

Pseudocode: Communicate an algorithm to another person.

insertion-sort(A, n)
A: array of size n
for (i <- i; i < n; i++) do
	for (j <- i; j > 0 and A[j-1] > A[j]; j--) do
		swap A[j] and A[j-1]

Omits obvious details, and should be precise about exit-conditions.

For problem $\Pi$ to program that solves it:

• Design an algorithm $\mathcal{A}$ that solves $\Pi$ $\to$ Algorithm Design.
• Assess correctness and efficiency of each $\mathcal{A}$ $\to$ Algorithm Analysis. Correctness $\to$ CS245.
• If acceptable, implement algorithms.
• If multiple acceptable algorithms, run experiments to determine the best solution.

This course will focus on the first two points.

Question

What do we mean by efficiency?

In this course, we are primarily concerned with the amount of time a program takes to run (run time).

We also may be interested in the amount of additional memory the program requires (auxiliary space).

The amount of time and or memory required by a program will usually depend on the given problem instance.

RAM model:

• Each memory cell stores one datum, typically a number, character, or reference.
• Any access to a memory location takes constant time.
• Any primitive operation takes constant time.

We compare algorithms by considering the growth rate: What is the behaviour of algorithms as size $n$ gets large?

We use order notation (big-$O$ and friends). Ignore constants and lower order terms.

We study relationships between functions.

Definition

$O$-notation: $f(x)\in O(g(x))$ ($f$ is asymptotically upper-bounded by $g$) if there exists constants $c>0$ and $n_0\ge 0$ such that $|f(x)|\le c|g(x)|$ for all $x\ge n_0$.

In order to prove that $2n^2+3n+11\in O(n^2)$ from first principles, we need to find $c$ and $n_0$ such that the following condition is satisfied:

$$\begin{array}{r}2n^2+3n+11\le c{n}^2\forall n\ge n_0\end{array}$$

Many, but not all, choices of $c$ and $n_0$ will work.

We also have that $2n^2+3n+11\in O(n^{10})$. We want a tight asymptotic bound.

Definition

$\Omega$-notation: $f(x)\in \Omega (g(x))$ ($f$ is asymptotically lower-bounded by $g$) if there exists constants $c>0$ and $n_0\ge 0$ such that $c|g(x)|\le |f(x)|$ for all $x\ge n_0$.

Definition

$\Theta$-notation: $f(x)\in \Theta (g(x))$ ($f$ is asymptotically tightly-bounded by $g$) if there exists constants $c_1$, $c_2$ $>0$ and $n_0\ge 0$ such that $c_1|g(x)|\le |f(x)|\le c_2|g(x)|\forall x\ge n_0$.

Equivalently:

$$\begin{array}{r}f(n)\in \Theta (g(n))⟺f(n)\in O(g(n))\wedge f(n)\in \Omega (g(n))\end{array}$$

We also say that the growth rates of $f$ and $g$ are the same.

How growth rates affect running time. It is interesting to see how the running time is affected when the size of the problem instance doubles.

$$\begin{array}{rlrl}\text{Constant complexity}:T(n)& =c& & ⇝T(2n)=c\\ \text{Logarithmic complexity}:T(n)& =c\log n& & ⇝T(2n)=T(n)+c\\ \text{Linear complexity}:T(n)& =cn& & ⇝T(2n)=2T(n)\\ \text{Linearithmic complexity}:T(n)& =cn\log n& & ⇝T(2n)=2T(n)+2cn\\ \text{Quadratic complexity}:T(n)& =c{n}^2& & ⇝T(2n)=4T(n)\\ \text{Cubic complexity}:T(n)& =c{n}^3& & ⇝T(2n)=8T(n)\\ \text{Exponential complexity}:T(n)& =c{2}^n& & ⇝T(2n)=(T(n){)}^2/c\end{array}$$

We have $f(n)=n\in \Theta (n)$.

Question

How to express that $f(n)$ grows slower than $n^2$.

Definition

$o$-notation: $f(x)\in o(g(x))$ ($f$ is asymptotically strictly smaller than $g$) if for all constants $c>0$, there exists a constant $n_0\ge 0$ such that $|f(x)|\le c|g(x)|\forall x\ge n_0$.

Definition

$\omega$-notation: $f(x)\in \omega (g(x))$ ($f$ is asymptotically strictly larger than $g$) if for all constants $c>0$, there exists a constant $n_0\ge 0$ such that $|f(x)|\ge c|g(x)|\forall x\ge n_0$.

Suppose that $f(n)>0$ and $g(n)>0$ for all $n\ge n_0$. Suppose that

$$\begin{array}{r}L=\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}\end{array}$$

Then

$$\begin{array}{r}f(n)\in \{\begin{array}{ll}o(g(n))& \text{if }L=0\\ \Theta (g(n))& \text{if }0<L<\infty \end{array}\end{array}$$

If the fraction goes towards $\infty$, then $f(n)\in \omega (g(n))$.

This can be computed using l’Hôspital’s rule. This result gives sufficient but not necessary conditions for the stated conclusion to hold.

Many rules are easily proved from first principle.

Identity rule: $f(n)\in \Theta (f(n))$.

Transitivity:

• If $f(n)\in O(g(n))$ and $g(n)\in O(h(n))$ then $f(n)\in O(h(n))$.
• If $f(n)\in \Omega (g(n))$ and $g(n)\in \Omega (h(n))$ then $f(n)\in \Omega (h(n))$.
• If $f(n)\in O(g(n))$ and $g(n)\in o(h(n))$ then $f(n)\in o(h(n))$.

Suppose that $f(n)>0$ and $g(n)>0$ for all $n\ge n_0$. Then:

• $f(n)+g(n)\in O(\max \{f(n),g(n)\})$
• $f(n)+g(n)\in \Omega (\max \{f(n),g(n)\})$

Relationships between order notations

$$\begin{array}{rl}f(n)\in \Theta (g(n))& ⟺g(n)\in \Theta (f(n))\\ f(n)\in O(g(n))& ⟺g(n)\in \Omega (f(n))\\ f(n)\in o(g(n))& ⟺g(n)\in \omega (f(n))\\ f(n)\in \Theta (g(n))& ⟺f(n)\in O(g(n))\wedge f(n)\in \Omega (g(n))\\ f(n)\in o(g(n))& ⟹f(n)\in O(g(n))\\ f(n)\in o(g(n))& ⟹f(n)\notin \Omega (g(n))\\ f(n)\in \omega (g(n))& ⟹f(n)\in \Omega (g(n))\\ f(n)\in \omega (g(n))& ⟹f(n)\notin O(g(n))\end{array}$$

Avoid doing arithmetic with asymptotic notations. Do not write $O(n)+O(n)=O(n)$.

Techniques for run-time analysis:

• Identify primitive operations that require $\Theta (1)$ time
• The complexity of a loop is expressed as the sum of the complexities of each iteration of the loop.
• Nested loops: start with the innermost loop and proceed outwards. This gives nested summations.

Let $T_{\mathcal{A}}(I)$ denote the running time of an algorithm $\mathcal{A}$ on instance $I$.

Worst-case (best-case) complexity of an algorithm: The worst-case (best-case) running time of an algorithm $\mathcal{A}$ is a function $T:{\mathbb{Z}}^{+}\to \mathbb{R}$ mapping $n$ to the longest (shortest) running time for any input instance of size $n$:

$$\begin{array}{rl}{T}_{\mathcal{A}}^{\text{worst}}(n)& =\underset{I\in {\mathcal{I}}_n}{\max }\{T_{\mathcal{A}}(I)\}\\ T_{\mathcal{A}}^{\text{best}}(n)& =\underset{I\in {\mathcal{I}}_n}{\min }\{T_{\mathcal{A}}(I)\}\end{array}$$

Average-case complexity of an algorithm: The average-case running time of an algorithm $\mathcal{A}$ is a function $T:{\mathbb{Z}}^{+}\to \mathbb{R}$ mapping $n$ to the average running time of $\mathcal{A}$ over all instances of size $n$:

$$\begin{array}{r}{T}_{\mathcal{A}}^{\text{avg}}(n)=\sum _{I\in {\mathcal{I}}_n}{T}_{\mathcal{A}}(I)\cdot (\text{relative frequency of }I)\end{array}$$

Question

Suppose algorithm ${\mathcal{A}}_1$ has worst-case run-time $O(n^3)$ and algorithm $A_2$ has worst-case run-time $O(n^2)$, and both the same problem. Is ${\mathcal{A}}_2$ more efficient?

No! $O$-notation is an upper-bound. ${\mathcal{A}}_1$ may well have worst-case run-time $O(n)$. We should always give $\Theta$-bounds.

Question

Suppose the run-times are $\Theta (n^3)$ and $\Theta (n^2)$, respectively. We consider ${\mathcal{A}}_2$ to be better. But is it always more efficient?

No! The worst-case run-time of ${\mathcal{A}}_1$ may only be achieved on some instances. Possibly ${\mathcal{A}}_1$ is better on most instances.

Merge-sort

Step 1: Describe the overall idea

Input: Array $A$ of $n$ integers.

1. We split $A$ into subarrays $A_L$ and $A_R$ that are roughly half as big.
2. Recursively sort $A_L$ and $A_R$
3. After $A_L$ and $A_R$ have been sorted, use a function merge to merge them into a single sorted array.

Step 2: Give pseudo-code or detailed description

merge-sort(A,n)
if (n <= 1) then return
else
	m = (n-1)/2
	merge-sort(A[0..m], m+1)
	merge-sort(A[m+1..n-1], r)
	merge(A[0..m], A[m +1...n-1])

Do not pass array $A$ by value, instead indicate the range of the array that needs to be sorted. merge an auxiliary array $S$. Allocate this only once.

merge(A,l,m,r,S)
A[0..n-1] is an array, A[l..m] is sorted, A[m+1..r] is sorted
S[0..n-1] is an array
copy A[l..r] into S[l..r]
(i_L, r_R) <- (l, m+1)
for (k <- l, k <= r: k++) do
	if (i_L > m) A[k] <- S[i_R ++]
	else if (i_R > r) A[k] <- S[i_L ++]
	else if (S[i_L] <= S[i_R]) A[k] <- S[i_L ++]
	else A[k] <- S[i_R ++]

Step 3: Argue correctness. Typically state loop-invariants. Sometimes obvious enough from idea-description and comments.

Step 3: Analyze the run-time

• First analyze work done outside recursion
• If applicable, analyze subroutines separately. If there are recursions: how big are the subproblems? The run-time then becomes a recursive function.

The recurrence relation for $T(n)$ is as follows

$$\begin{array}{r}T(n)=\{\begin{array}{ll}T\left(\lfloor \frac{n}{2}\rfloor \right)+T\left(\lfloor \frac{n}{2}\rfloor \right)+cn& \text{if }n>1\\ c& \text{if }n=1\end{array}\end{array}$$

The following is the corresponding sloppy recurrence

$$\begin{array}{r}T(n)=\{\begin{array}{ll}2T\left(\frac{n}{2}\right)+cn& \text{if }n>1\\ c& \text{if }n=1\end{array}\end{array}$$

This resolves to $T(n)\in O(n\log n)$.

Module 2

Definition

Abstract Data Type (ADT): A description of information and a collection of operations on that information. (Covered in CS135).

The information is accessed only through the operations.

We can have various realizations of an ADT, which specify how the information is stored and how the operations are performed.

Recall:

Stack: An ADT consisting of a collection of items with operations:

• push: Add an item to the stack.
• pop: Remove and return the most recently added item.

Items are removed in LIFO order. We can have extra operations size, is-empty, and top.

Queue: An ADT consisting of a collection of items with operations:

• enqueue: Add an item to the queue
• dequeue: Remove and return the least recently inserted item.

Items are removed in FIFO order.

We can have extra operations size, is-empty, and peek/format.

Priority Queue generalizes both ADT Stack and ADT Queue.

It is a collection of items (each with a priority or key) with operations:

• insert: Inserting an item tagged with a priority
• delete-max: Removing and returning an item of highest priority.

We can have extra operations: size, is-empty, get-max.

This is a maximum-oriented priority queue. A minimum-oriented priority queue replaces operation delete-max by delete-min.

Using a priority queue to sort:

PQ-Sort(A[0..n-1])
for i <- 0 to n-1 do
	PQ.insert (an item with priority A[i])
for i <- n-1 down to 0 do
	A[i] <- priority of PQ.delete-max()

Written as: $O$(initialization $+n\cdot$ insert + $n\cdot$ delete-max$)$

Realizations of Priority Queues

Realization 1: Unsorted arrays

Run-time of operations:

• insert: $\Theta (1)$
• delete-max: $\Theta (n)$

We assume dynamic arrays, expand by doubling as needed. Amortized over all insertions this takes $\Theta (1)$ extra time.

PQ-sort with this realization yields selection-sort.

Realization 2: Sorted arrays

Run-time of operations:

• insert: $\Theta (n)$
• delete-max: $\Theta (1)$

PQ-sort with this realization yields insertion-sort. insert can be implemented to have $\Theta (1)$ best-case run-time. insertion-sort then has $\Theta (n)$ best-case run-time.

Realization 3: Heaps

A binary heap is a certain type of binary tree. A binary tree is either empty, or consists of a node and two binary trees (left subtree and right subtree).

Level $\ell =$ all nodes with $\ell$ distance from the root. Root is on level $0$.

Height $h=$ maximum number for which level $h$ contains nodes. Single-node tree has height $0$, empty tree has height $-1$.

Any binary tree with height $h$ has $n\le 2^{h+1}-1$ nodes. So height $h\le \log (n+1)-1\Omega (\log n)$.

A heap is a binary tree with the following two properties:

1. Structural property: All the levels of a heap are completely filled, except possibly for the last level. The filled items in the last level are left-justified.
2. Heap-order property: For any node $i$, the key of the parent of $i$ is larger than or equal to key of $i$.

The full name for this is max-oriented binary heap.

Lemma: The height of a heap with $n$ nodes is $\Theta (\log n)$.

Heaps should not be stored as binary trees. Let $H$ be a heap of $n$ items and let $A$ be an array of size $n$. Store root in $A[0]$ and continue with elements level-by-level from top to bottom, in each level-to-right.

It is easy to navigate using this array representation:

• The root node is at index 0
• The last node is $n-1$
• The left child is of node $i$ is node $2i+1$
• The right child of node $i$ is node $2i+2$
• The parent of node $i$ is node $\lfloor \frac{i-1}{2}\rfloor$
• These nodes exist if the index falls in the range $\{0,\dots ,n-1\}$

We hide implementation details using helper-functions.

insert in heaps: Place the new key at the first free leaf. Use fix-up to restore heap order.

insert(x)
l <- last()+ 1
A[l] <- x
increase size
fix-up(A, l)

fix-up(A,i)
while parent(i) exists and A[parent(i)].key < A[i].key do
	swap A[i] and A[parent(i)]
	i <- parent(i)

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

delete-max in heaps

The maximum item of a heap is just the root node. We replace the root by the last leaf (last leaf is taken out). The heap-order property might be violated, perform a fix-down.

fix-down(A,i)
while i is not a leaf do
	j <- left child of i
	if (i has right child and A[right child of i].key > A[j].key)
		j <- right child of i
	if A[i].key >= A[j].key break
	swap A[j] and A[i]
	i <- j

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

delete-max()
l <- last()
swap A[root()] and A[l]
decrease size
fix-down(A, root(), size)
return A[l]

Time: $O($ height of heap $)=O(\log n)$ (and this is tight).

Binary heap are a realization of priority queues where the operations insert and delete-max take $\Theta (\log n)$ time.

Any priority queue can be used to sort in time

Using the binary-heaps implementation of PQs, we obtain:

PQ-sort-with-heaps(A)
for i <- 0 to n-1 do
	H.insert(A[i])
for <- n-1 down to 0 do
	A[i] <- H.delete-max()

Both operations run in $O(\log n)$ time for heaps $⇝$ PQ-sort using heaps takes $O(n\log n)$ time.

Can improve this with two simple tricks $\to$ heap-sort.

1. Can use the same array for input and heap $⇝O(1)$ auxiliary space.
2. Heaps can be built faster if we know all input in advance.

Problem: Given $n$ items all at once (in $A[0\cdots n-1]$) build a heap containing all of them.

Solution 1: Start with an empty heap and insert items one at a time.

simple-heap-building(A)
for i <- 0 to A.size() - 1 do
	H.insert(A[i])

This corresponds to doing fix-up’s. Worst-case running time: $O(n\log n)$

We can use fix-down’s instead.

heapify(A)
n <- A.size()
for i <- parent(last()) downto root() do
	fix-down(A, i, n)

This yields a worst-case complexity of $\Theta (n)$. A heap can be built in linear time.

Efficient sorting with heaps: Idea is to use PQ-sort with heaps.

heap-sort()A
n <- A.size()
for i <- parent(last()) downto 0 do
	fix-down(A,i,n)
 
while n > 1
	swap items at A[root()] and A[last()]
	decrease n
	fix-down(A, root(), n)

The for-loop takes $\Theta (n)$ time and the while-loop takes $\Theta (n\log n)$ time.

Problem: Find the $k$th smallest item in an array $A$ of $n$ numbers.

Solution 1: Make $k+1$ passes through the array, deleting the minimum number each time. Complexity $\Theta (kn)$.

Solution 2: Sort $A$, then return $A[k]$. Complexity $\Theta (n\log n)$.

Solution 3: Create a min-heap with heapify(A). Call delete-min(A) $k+1$ times. Complexity: $\Theta (n+k\log n)$.

Question

We can achieve $\Theta (n\log n)$ worst-case time easily, but can we do better?

Yes.

Module 3

We introduce (and solve) a new problem, and then analyze the average-case run-time of our algorithm.

Recall the definition of average-case run-time:

$$\begin{array}{r}{T}_{\mathcal{A}}^{\text{avg}}(n)=\sum _{\text{instance }I\text{ of size }n}{T}_{\mathcal{A}}(I)\cdot (\text{relative frequency of }I)\end{array}$$

Assume that the set ${\mathcal{I}}_n$ of size-$n$ instances is finite. Assume that all instances can occur equally frequently. Then we can use the following simplified formula

$$\begin{array}{r}{T}^{\text{avg}}(n)=\frac{{\sum }_{I:\mathrm{size}(I)=n}T(I)}{\#\text{instances of size }n}=\frac{1}{|{\mathcal{I}}_n|}\sum _{i\in {\mathcal{I}}_n}T(I)\end{array}$$

To learn how to analyze this, we will do simpler examples first.

silly-test(π, n)
π: a permutation of {0, ..., n-1}, stored as an array
if π[0] = 0 then for j = 1 to n do print 'bad case'
else print 'good case'

$$\begin{array}{r}{T}^{\text{avg}}(n)=\frac{1}{n!}\sum _{\pi \in {\Pi }_n}T(\pi )=\frac{1}{n!}\left(\sum _{\begin{array}{c}\pi \in {\Pi }_n\\ \text{in bad case}\end{array}}T(\pi )+\sum _{\begin{array}{c}\pi \in {\Pi }_n\\ \text{in good case}\end{array}}T(\pi )\right)\end{array}$$

$(n-1)!$ permutations have $\pi [0]=0⟹$ run-time $c\cdot n$. The remaining $n!-(n-1)!$ permutations have run-time $c$.

$$\begin{array}{rl}{T}^{\text{avg}}(n)& =\frac{1}{n!}\left(\#\{\pi \in {\Pi }_n\text{ in base case}\}\cdot cn+\#\{\pi \in {\Pi }_n\text{ in good case}\}\cdot c\right)\\ & =\frac{1}{n!}\left((n-1)!\cdot cn+(n!-(n-1)!)\cdot c\right)\le \frac{1}{n}cn+c=2c\in O(1)\end{array}$$

Another not-so-contrived example

all-0-test(w,n)
// test whether all entries of bitstring w[0..n-1] are 0
if (n=0) return true
if (w[n-1] = 1) return false
all-0-test(w,n-1)

Define $T(w)=\#$ bit-comparisons on input $w$. This is asymptotically the same as the run-time.

Worst-case run-time: Always go into the recursion until $n=0$. $T(n)=1+T(n-1)=1+1+\cdots +T(0)=n\in \Theta (n)$.

Best-case run-time: Return immediately. $T(n)=1\in \Theta (1)$.

Average-case run-time?

Recall $T^{\text{avg}}(n)=\frac{1}{|{\mathcal{B}}_n|}{\sum }_{w\in {\mathcal{B}}_n}T(w)$ \quad ${\mathcal{B}}_n=\{\text{bistrings of length }n\}$.

Recursive formula for one non-empty bitstring $w$:

$$\begin{array}{r}T(w)=\{\begin{array}{ll}1& \text{if }w[n-1]=1\\ 1+T(\underset{\text{length }n-1}{\underbrace{w[\mathrm{0..}n-2]}})& \text{otherwise}\end{array}\end{array}$$

Natural guess for the recursive formula for $T^{\text{avg}}(n)$:

$$\begin{array}{r}{T}^{\text{avg}}(n)=\underset{\begin{array}{c}\text{half have}\\ w[n-1]=1\end{array}}{\underbrace{\frac{1}{2}}}\cdot 1+\underset{\begin{array}{c}\text{half have }\\ w[n-1]=0\end{array}}{\underbrace{frac12}}(1+T^{???}(n-1))\end{array}$$

This holds with $\le$ but is useless if ??? is worst. This is not obvious if ??? is avg.

$$\begin{array}{rl}{T}^{\text{avg}}(n)& =\frac{1}{|{\mathcal{B}}_n|}\sum _{x\in {\mathcal{B}}_n}T(w)\\ & =\frac{1}{|{\mathcal{B}}_n|}\sum _{\begin{array}{c}x\in {\mathcal{B}}_n\\ w[n-1]=1\end{array}}1+\frac{1}{|{\mathcal{B}}_n|}\sum _{\begin{array}{c}x\in {\mathcal{B}}_n\\ w[n-1]=0\end{array}}\left(1+T(w[\mathrm{0..}n-2])\right)\\ & =\frac{1}{2}+\frac{1}{2}+\frac{1}{|{\mathcal{B}}_n|}\sum _{w^{\prime }\in {\mathcal{B}}_n-1}\sum _{\begin{array}{c}w\in {\mathcal{B}}_n\\ w[n-1]=0\\ w[\mathrm{0..}n-2]=w^{\prime }\end{array}}T(w^{\prime })\end{array}$$

Observe: $w$ is uniquely determined by $w^{\prime }$ and $w[n-1]=0$.

$$\begin{array}{rl}& =1+\frac{1}{|{\mathcal{B}}_n|}\sum _{w^{\prime }\in {\mathcal{B}}_{n-1}}T(w^{\prime })\\ & =1+\frac{|{\mathcal{B}}_{n-1}|}{|{\mathcal{B}}_n|}\frac{1}{|{\mathcal{B}}_{n-1}|}\sum _{w^{\prime }\in {\mathcal{B}}_{n-1}}T(w^{\prime })=1+\frac{1}{2}{T}^{\text{avg}}(n-1)\end{array}$$

This recursion resolves $T^{\text{avg}}(n)\in O(1)$.

Question

Why can’t we always write ‘avg’ for ’???’ in $T^{\text{avg}}(n)=1+\frac{1}{2}{T}^{???}(n-1)$?

Consider

silly-all-0-test(w,n)
if (n = 0) then return true
if (w[n-1] = 1) then return false
if (n>1) then w[n-2] <- 0
silly-all-0-test(w,n-1)

Only one more line of code in each recursion, so same formula applies.

But observe that now $T(w)=\{\begin{array}{ll}1& \text{if }w[n-1]=1\\ n& \text{if }w[n-1]=0\end{array}$

So $T^{\text{avg}}(n)=1+\frac{n}{2}\in \Theta (n)$. The ‘obvious’ recursion did not hold. Average-case analysis is highly non-trivial for recursive algorithms.

We saw SELECTION: Given an array $A$ of $n$ numbers, and $0\le k<n$, find the element that would be at position $k$ of the sorted array.

SELECTION can be done with heaps in time $\Theta (n+k\log n)$.

Special case: MEDIANFINDING = SELECTION with $k=\lfloor \frac{n}{2}\rfloor$. With previous approaches, this takes time $\Theta (n\log n)$, no better than sorting.

Question

Can we do selection in linear time?

Yes, the algorithm quick-select.

quick-select and the related quick-sort rely on two subroutines:

• choose-pivot(A): Return an index $p$ in $A$. We will use the pivot-value $v\leftarrow A[p]$ to rearrange the array.
• partition(A,p): Rearrange $A$ and return pivot-index $i$ so that
  • the pivot-value $v$ is in $A[i]$,
  • all items in $A[0,\dots ,i-1]$ are $\le v$, and
  • all items in $A[i+1,\dots ,n-1]$ are $\ge v$.

$p=$ index of pivot-value before partition (we choose it), $i=$ index of pivot-value after partition (no control).