1 of 45

Lecture 10

More divide and conquer (runtimes, matrix multiplication)

CSE 421 Autumn 2025

1

2 of 45

Previously…

2

3 of 45

The Divide and Conquer paradigm

3

  1. Divide the instance into parts
  2. Solve the parts recursively (meaning divide each part into subparts, subparts into subsubparts, etc..)
  3. Conquer by combining the answers in each layer to get the answer for the layer above, and so on.

4 of 45

A classic divide and conquer problem

Mergesort

  •  

4

5 of 45

A classic divide and conquer problem

Mergesort

  •  

5

6 of 45

A classic divide and conquer problem

Mergesort

  •  

6

7 of 45

A classic divide and conquer problem

Mergesort

  •  

7

8 of 45

A classic divide and conquer problem

Mergesort

  •  

8

9 of 45

A classic divide and conquer problem

Mergesort

  •  

9

 

 

and

 

Time to sort two instances of half the size

Time to merge

10 of 45

A classic divide and conquer problem

Mergesort

  •  

10

 

 

and

 

 

11 of 45

2D Euclidean closest pair

  •  

11

12 of 45

The entire algorithm

  •  

 

 

13 of 45

The entire algorithm

  •  

 

 

 

14 of 45

Main takeaway

14

To make divide and conquer efficient/worth it, your conquer step must be faster than your baseline algorithm.

15 of 45

Today

15

More Divide and Conquer:

  • Runtimes
  • Matrix Multiplication, Integer Multiplication

16 of 45

Divide and conquer runtimes

The master theorem

  •  

16

17 of 45

Divide and conquer runtimes

The master theorem

  •  

17

18 of 45

Intuition for the master theorem

    • Calculate the amount of work done by the “conquer” step at each level
    • Count how many levels of computation there are

18

 

 

 

 

 

Due to recursion, the problem has a tree like structure

Proof strategy:

19 of 45

Divide and conquer runtimes

  •  

The master theorem

19

20 of 45

Divide and conquer runtimes

  •  

The master theorem

20

21 of 45

Divide and conquer runtimes

  •  

The master theorem

21

 

22 of 45

Matrix multiplication

  •  

22

23 of 45

Trivial algorithm for matrix multiplication

  •  

23

 

Can we do better?

24 of 45

Matrix multiplication naturally decomposes

Matrix multiplication decomposes into smaller matrix multiplications!�

24

Divide and conquer algorithm idea:

 

 

Runtime:

 

 

25 of 45

Matrix multiplication naturally decomposes

Matrix multiplication decomposes into smaller matrix multiplications!�

25

Divide and conquer algorithm idea:

 

 

Runtime:

 

 

26 of 45

Matrix multiplication naturally decomposes

Matrix multiplication decomposes into smaller matrix multiplications!�

26

Divide and conquer algorithm idea:

 

Runtime:

 

 

 

So, we didn’t gain anything..

What should we try to do to make divide and conquer work?

27 of 45

Strassen’s divide and conquer (1968)

  •  

27

Previously: we were directly multiplying, and then adding:

28 of 45

Strassen’s divide and conquer (1968)

28

29 of 45

Strassen’s divide and conquer (1968)

29

30 of 45

Strassen’s divide and conquer (1968)

30

31 of 45

Strassen’s divide and conquer (1968)

31

32 of 45

Strassen’s divide and conquer (1968)

32

33 of 45

Strassen’s divide and conquer (1968)

33

34 of 45

A decomposition from another planet

34

Wikipedia article for Strassen’s algorithm

 

Previously, we computed 8 small matrices (one for each green square via one multiplication), and obtained the C matrices by additions of these 8 matrices.

35 of 45

A decomposition from another planet

35

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)?

36 of 45

A decomposition from another planet

36

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

2

37 of 45

A decomposition from another planet

37

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

 

38 of 45

A decomposition from another planet

38

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

 

39 of 45

A decomposition from another planet

39

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

 

40 of 45

A decomposition from another planet

40

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

41 of 45

A decomposition from another planet

41

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

42 of 45

A decomposition from another planet

42

Wikipedia article for Strassen’s algorithm

 

What if I told you.. you can obtain the C matrices by adding together just 7 matrices (each obtained via one multiplication)? These are the 7 matrices:

Wikipedia article for Strassen’s algorithm

43 of 45

A decomposition from another planet

43

Wikipedia article for Strassen’s algorithm

44 of 45

Strassen’s algorithm

44

 

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

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

45 of 45

Strassen’s algorithm

  •  

45