Lecture 12

Even faster median finding

CSE 421 Autumn 2026

1

Previously…

2

“Selection” finding

Input: pair .

Output: The -th element when .

3

Median finding is just Selection finding for .

Can solve Selection finding in time by sorting, and then selecting the -th element.

Is achievable?

The recurrence relation we are shooting for:

Crucially, there is a single branch in this recursion!

Selection finding

Find the 6th element

4

The idea:

Inspired by the Quicksort “pivot” approach:

• We’ll pick a uniformly random element as a “pivot”.
• Divide the array into 3 subsets: elements equal, larger, smaller than pivot.
• Figure out which subset the 6th element belongs to.
• Recurse, i.e. solve Selection finding on the one subset that contains the 6th element!

The good news: only one branch!

But is our instance size 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

In , since

length 9

length 4

length 7

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?

In , since

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 , since and

In fact, in this case, the 6th element is exactly the pivot! So we just output it right away.

Selection finding

Randomized algorithm :

• Randomly sample from . Call the pivot.
• Filter into , , and based on if , , or .
• Case 1: . Run .
• Case 2: and . Output .
• Case 3: . Run .

17

Runtime analysis

• Our processing (sampling + filtering + identifying case) takes linear time: for some constant .
• In order to apply the master theorem, we would need to argue that each recursive call is reducing the input size from to for some constant . Then, we would have:
• However, each call may not reduce the size from to . The new size depends on how close the randomly chosen is to the middle!
• For example, what if we are unlucky and pivot is the unique largest element?

18

Runtime analysis

• Our processing (sampling + filtering + identifying case) takes linear time: for some constant .
• In order to apply the master theorem, we would need to argue that each recursive call is reducing the input size from to for some constant . Then, we would have:
• However, each call may not reduce the size from to . The new size depends on how close the randomly chosen is to the middle!
• For example, what if we are unlucky and pivot is the unique largest element? Then , and . Instance size decreases only from to .
• Fortunately, the latter occurs only with probability .

19

Runtime analysis

Expected runtime analysis:

• If pivot is the -th element, then the next problem is of size .
• With probability , pivot is the -th element for .
• Whenever the latter happens, we are guaranteed that the next problem size is at most . So, this is a good pivot!
• How many steps does it take in expectation to find a good pivot?

20

Runtime analysis

Expected runtime analysis:

• If pivot is the -th element, then the next problem is of size .
• With probability , pivot is the -th element for .
• Whenever the latter happens, we are guaranteed that the next problem size is at most . So, this is a good pivot!
• In expectation, it takes two steps to get a good pivot. So, in expectation, it takes time to shrink the instance size from to .

Total expected runtime: .

21

Today

22

• Median/selection finding: a deterministic algorithm

Selection finding

• We achieved expected runtime. Pretty cool.
• FYI: the worst-case runtime is (e.g. if we are always unlucky and always pick the pick the pivot to be the largest element). But this only happens with probability probability.
• Randomness was crucial, and does feel necessary to achieve .

23

.. but is it?

Blum-Floyd-Pratt-Rivest-Tarjan (1973): Selection/median finding can be done in deterministic time .

Pivot selection algorithm (BFPRT ‘73)

• Express the elements as a matrix of elements

24

Pivot selection algorithm (BFPRT ‘73)

• Express the elements as a matrix of elements
• Calculate the medians of each of the columns:

25

Pivot selection algorithm

• Express the elements as a matrix of elements
• Calculate the medians of each of the columns:

26

Pivot selection algorithm

• Express the elements as a matrix of elements
• Calculate the medians of each of the columns:
• Choose the pivot as the median of the medians:

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

i.e. that the pivot is the -th element for some .

Pivot selection algorithm

Proof of correctness

• Half of the columns are �such that .

29

i.e. that the pivot is the -th element for some .

Pivot selection algorithm

Proof of correctness

• There are columns such that .

30

i.e. that the pivot is the -th element for some .

Pivot selection algorithm

Proof of correctness

• There are columns such that .
• In each such column, there are 3 elements .

31

i.e. that the pivot is the -th element for some .

Pivot selection algorithm

Proof of correctness

• There are columns such that .
• In each such column, there are 3 elements .
• Therefore, there are elements.
• Similarly, there are elements .

32

So, is in the middle elements and a good pivot!

With this pivot, the next instance�would be of size at most

i.e. that the pivot is the -th element for some .

Pivot selection algorithm

Runtime analysis

• Express the elements as a matrix of elements
• Calculate the medians of each of the columns:
• Choose the pivot as the median of the medians:

33

The last runtime is in terms of (time to compute median on size )! This is a creative approach! But still unclear if this actually helps us..

Median/Selection finding algorithm (BFPRT ’73)

Selection:

• Calculate median-of-medians() in a representation.
• Filter into , , and based on if , , or .
• Case 1:. Run Selection.
• Case 2: and . Output .
• Case 3:. Run Selection.

34

Runtime:

Median/Selection finding algorithm (BFPRT ’73)

Selection:

• Calculate median-of-medians() in a representation.
• Filter into , , and based on if , , or .
• Case 1:. Run Selection.
• Case 2: and . Output .
• Case 3:. Run Selection.

35

Runtime:

Median/Selection finding algorithm (BFPRT ’73)

36

Runtime:

Why?

Let the term be bounded by for some constant . We’ll check directly by substitution that is a solution for a large enough constant .

So the runtime is at most .

(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!