1 of 37

Lecture 11

More divide and conquer (integer multiplication & median finding)

CSE 421 Autumn 2026

1

2 of 37

Previously…

2

3 of 37

Divide and conquer runtimes

  • Suppose you know:� and
  • Different cases based on how , and compare:
    • If , then
    • If , then
    • If , then

The master theorem

3

Note: . The latter is exactly the number of leaves!

4 of 37

Matrix multiplication

Matrix multiplication decomposes into smaller matrix multiplications!�

4

Divide and conquer algorithm idea:

Divide: Decompose into 8 matrix multiplications of matrices�

Conquer: “Merge” by performing 4 matrix additions of matrices

Runtime:

Each one takes

Each one takes

5 of 37

Strassen’s divide and conquer (1968)

There is a way to decompose into 7 multiplications and 18 additions …

​

5

Previously: we were directly multiplying, and then adding:

- Volker Strassen (90 years old!) about his algorithm

“It is really very simple. I was surprised that nobody had found it before.”

6 of 37

Strassen’s divide and conquer (1968)

6

Wikipedia article for Strassen’s algorithm

2

7 of 37

Today

7

More Divide and Conquer:

  • Integer multiplication
  • Median finding

8 of 37

Integer multiplication

Input: Two -bit binary numbers

Output: Their product (a -bit binary number)

8

Gradeschool multiplication algorithm takes time

Note: this is not in the word-RAM model. Instead, it’s counting the number of binary operations

9 of 37

Karatsuba’s algorithm

9

4 smaller multiplications

Similarly as in Strassen’s algorithm, �decompose each number into parts�(here two halves: most and least significant digits)

We can add numbers in time. And also multiply by (why?)

10 of 37

Karatsuba’s algorithm

10

4 smaller multiplications

Similarly as in Strassen’s algorithm, �decompose each number into parts�(here two halves: most and least significant digits)

11 of 37

Karatsuba’s algorithm

11

Can we do it with just 3 multiplications?

12 of 37

Karatsuba’s algorithm

12

Can we do it with just 3 multiplications?

Yes!

13 of 37

Karatsuba’s algorithm

13

Can we do it with just 3 multiplications?

Yes!

14 of 37

Karatsuba’s algorithm

14

Can we do it with just 3 multiplications?

Yes!

15 of 37

Improving integer multiplication

  • Karatsuba’s algorithm is not the fastest
  • Fastest (asymptotically) used to be based on the Fast Fourier Transform.
  • Fast Fourier Transform was sped up (asymptotically) in a breakthrough from OpenAI’s 2026 release. New runtime is , shattering a longstanding belief that was optimal!
  • The asymptotic advantage only kicks in at extremely large . Karatsuba or other algorithms are faster for most use cases.

15

16 of 37

Multiplication

  • Matrix multiplication
    • time algorithm for matrices (Strassen’s divide and conquer algorithm)
    • Fastest known (asymptotically) is [OpenAI 2026]
  • Integer multiplication
    • time algorithm for multiplying -bit numbers (Karatsuba’s divide and conquer algorithm)
    • Fastest (asymptotically) is via Fast Fourier Transform and OpenAI’s latest improvement on it.

16

17 of 37

Median finding

Input: Input list for odd.

Output: The median element i.e. when .

17

Can do it in time using sorting + selecting the middle element.

Is achievable?

Seems impossible…

… but we’ve seen other seemingly impossible things in this course

18 of 37

Median finding

18

Let’s try to design a divide and conquer algorithm.

What would the recurrence relation have to look like to have ?

Two natural possibilities:

Possibility 1:

Possibility 2:

Leaf-heavy computation

The challenge would be to split the input into two halves with compute.�And to “merge” the solutions to the two subproblems together also in compute

With time, we can make a constant number of passes through the input .�After a constant number of passes, we need to find one sublist of size which must contain the median. Then, recurse.

Most compute in largest conquer step

19 of 37

“Selection” finding

It will help us to consider a generalization of the median finding problem, called “Selection” finding.

Input: pair .

Output: The -th element when .

19

Median finding is just Selection finding for .

20 of 37

Selection finding

Find the 6th element

20

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

21 of 37

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

22 of 37

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

23 of 37

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

24 of 37

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

In , since

length 9

length 4

length 7

Recurse on this set

25 of 37

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

26 of 37

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

27 of 37

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

28 of 37

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?

In , since

Recurse on this set

29 of 37

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

30 of 37

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

31 of 37

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

32 of 37

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

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

33 of 37

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 .

33

Note that the original -th element will now be the -th!

34 of 37

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?

34

35 of 37

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 .

35

36 of 37

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?

36

37 of 37

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: .

37