Lecture 11
More divide and conquer (median finding)
CSE 421 Autumn 2025
1
Previously…
2
Divide and conquer runtimes
The master theorem
3
Matrix multiplication
Matrix multiplication decomposes into smaller matrix multiplications!�
4
Divide and conquer algorithm idea:
Runtime:
Strassen’s divide and conquer (1968)
5
Previously: we were directly multiplying, and then adding:
- Volker Strassen (89 years old!) about his algorithm
“It is really very simple. I was surprised that nobody had found it before.”
Strassen’s divide and conquer (1968)
6
Wikipedia article for Strassen’s algorithm
2
Today
7
More Divide and Conquer:
Integer multiplication
8
Note: this is not in the word-RAM model. Instead, it’s counting the number of binary operations
Karatsuba’s algorithm
9
4 smaller multiplications
Karatsuba’s algorithm
10
4 smaller multiplications
Karatsuba’s algorithm
11
Can we do it with just 3 multiplications?
Karatsuba’s algorithm
12
Can we do it with just 3 multiplications?
Yes!
Karatsuba’s algorithm
13
Can we do it with just 3 multiplications?
Yes!
Karatsuba’s algorithm
14
Can we do it with just 3 multiplications?
Yes!
Improving integer multiplication
15
Multiplication
16
Median finding
17
Seems impossible…
… but we’ve seen other seemingly impossible things in this course
Median finding
18
Let’s try to design a divide and conquer algorithm.
Two natural possibilities:
Leaf-heavy computation
Most compute in largest conquer step
“Selection” finding
19
Selection finding
Find the 6th element
20
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
21
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
22
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
23
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
24
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
25
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
26
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
27
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
28
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
29
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
30
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
31
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
32
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
33
Runtime analysis
34
Runtime analysis
35
Runtime analysis
36
Runtime analysis
37