Lecture 12
Wrap up median finding & start Dynamic Programming
CSE 421 Autumn 2025
1
Previously…
2
“Selection” finding
3
Crucially, there is a single branch in this recursion!
Selection finding
Find the 6th element
4
The idea:
Inspired by the Quicksort “pivot” approach:
The good news: only one branch!
But is our instance shrinking fast enough?
Depends on how lucky/unlucky we are with the pivot..
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Selection finding with pivot (examples)
Find the 6th element
5
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Selection finding with pivot (examples)
Find the 6th element
6
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
7
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
8
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
3
3
3
3
0
1
1
2
0
1
2
2
2
7
4
4
8
6
6
5
Where is the 6th element?
Randomly select a pivot
length 9
length 4
length 7
Recurse on this set
Selection finding with pivot (examples)
Find the 6th element
9
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Selection finding with pivot (examples)
Find the 6th element
10
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
11
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
12
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
length 2
length 3
length 15
Where is the 6th element?
Recurse on this set
Selection finding with pivot (examples)
Find the 6th element
13
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Selection finding with pivot (examples)
Find the 6th element
14
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
15
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
Selection finding with pivot (examples)
Find the 6th element
16
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
Randomly select a pivot
0
0
1
1
1
2
2
2
2
7
3
3
3
3
4
4
8
6
6
5
length 5
length 4
length 11
Where is the 6th element?
In fact, in this case, the 6th element is exactly the pivot! So we just output it right away.
Selection finding
17
Runtime analysis
18
Runtime analysis
19
Runtime analysis
20
Runtime analysis
21
Today
22
Selection finding
23
.. but is it?
Pivot selection algorithm (BFPRT ‘73)
24
Pivot selection algorithm (BFPRT ‘73)
25
Pivot selection algorithm
26
Pivot selection algorithm
27
This should give you pause: this pivot algorithm is supposed to be used as a subroutine within an algorithm that computes the median! So how can we compute this median?
Recursion as usual!
Pivot selection algorithm
Proof of correctness
28
Pivot selection algorithm
Proof of correctness
29
Pivot selection algorithm
Proof of correctness
30
Pivot selection algorithm
Proof of correctness
31
Pivot selection algorithm
Runtime analysis
32
Not really a step, just an interpretation
Median/Selection finding algorithm (BFPRT ’73)
33
this is recursive: will make more calls to Selection()
Median/Selection finding algorithm (BFPRT ’73)
34
this is recursive: will make more calls to Selection()
Why?
Median/Selection finding algorithm (BFPRT ’73)
35
Why?
(We are implicitly assuming that a recurrence relation has a unique solution - which is the case once you specify the initial condition, since subsequent runtimes are determined uniquely by the prior ones)
Note: to get a linear time, it’s crucial that the two fractions sum to less than 1!