Recitation 1: Matrix Multiplication and the Master Theorem

What this lecture covers

This recitation, taught by TA Ling Ren, follows up on the first two 6.046 lectures. It first tightens the weighted interval scheduling dynamic program from the earlier lecture, showing how sorting requests by start time reduces the number of subproblems from quadratic to linear. It then introduces Strassen's algorithm for matrix multiplication as a new divide-and-conquer example and uses it to motivate the Master Theorem, a general tool for solving divide-and-conquer recurrences.

After watching, you can explain why solving weighted interval scheduling by start time rather than by trying every request as "first" cuts the recursion's complexity, state the three cases of the Master Theorem, and apply it (or, when it doesn't apply, a direct inductive argument) to recurrences like Strassen's and the median-of-medians recurrence from Lecture 2.

Key ideas

• Redundant subproblems: the lecture's original weighted interval scheduling DP tries every request as a possible "first" request, which creates overlapping recursive calls and, once memoized, still costs Theta(n^2) because later requests query many earlier subproblems.
• Sorting by start time: processing requests in order of start time and asking a binary "include this request or not" question at each step produces only Theta(n) distinct subproblems and an O(n log n) algorithm overall (dominated by the initial sort).
• Recursion trees: drawing the tree of subproblems, and counting how much work happens at each level, is the general technique used to analyze both the interval scheduling recursion and the Master Theorem's cases.
• Blocked matrix multiplication: splitting two n x n matrices into four n/2 x n/2 quadrants and combining the standard eight sub-multiplications gives T(n) = 8T(n/2) + Theta(n^2), which is still Theta(n^3), no improvement over the naive algorithm.
• Strassen's algorithm: by combining quadrants into seven cleverly chosen products (M1 through M7) instead of eight, Strassen's algorithm gets T(n) = 7T(n/2) + Theta(n^2), which the Master Theorem shows is Theta(n^log2(7)), roughly Theta(n^2.81).
• Master Theorem: for T(n) = a*T(n/b) + f(n), compare f(n) to n^(log_b(a)): if f(n) grows strictly slower, T(n) = Theta(n^(log_b(a))); if comparable (with a log factor), there is a middle case; if f(n) dominates, T(n) = Theta(f(n)).
• When the Master Theorem doesn't apply: recurrences like T(n) = T(n/5) + T(7n/10) + Theta(n), with two differently sized recursive calls, require a direct inductive proof instead, substituting an assumed bound T(n) <= K*n and checking that the inequality holds for a large enough constant K.

Walkthrough

Recitation intro (0:20)

Ling Ren introduces himself as one of the two TAs alternating weekly sections and explains that this recitation will fill in open questions from the week's two lectures on divide and conquer, plus cover a new algorithm.

Improving weighted interval scheduling (2:16)

The recitation recaps the lecture's DP, which tries each request j as a possible first pick and recurses on R(j), the set of requests starting after j finishes, giving Theta(n^2) time even with memoization because later requests in the ordering revisit many overlapping subproblems. Students identify the inefficiency: some candidates, like starting from request 3 when request 2 could also start there, are strictly dominated. The fix is to sort requests by start time and, for the earliest-starting request, ask only two questions: schedule it or don't. Not scheduling it leaves the subproblem on the remaining n-1 requests; scheduling it jumps to R(j). Because each level of this recursion asks a constant amount of work and there are only Theta(n) distinct subproblems, the recursion tree analysis gives Theta(n) for the recursive step and O(n log n) overall once the initial sort is included, compared to Theta(n^2) for the naive version's recursion tree, where the work at each level grows with the number of branches.

Strassen's algorithm for matrix multiplication (22:40)

Ren introduces matrix multiplication as a widely used primitive and shows that naive blocked multiplication, splitting each matrix into four quadrants and computing all eight quadrant products, still costs Theta(n^3) because T(n) = 8T(n/2) + Theta(n^2) solves to the same complexity as the standard algorithm. Strassen's 1969 algorithm instead defines seven auxiliary matrix products M1 through M7 from combinations of the quadrants, from which all four output quadrants can be reconstructed using only additions and subtractions; the recitation verifies one output quadrant (C21 = M2 + M4) as an example without deriving the full set. Because only seven multiplications are needed instead of eight, the recurrence becomes T(n) = 7T(n/2) + Theta(n^2).

The Master Theorem (33:13)

To solve recurrences like Strassen's, the recitation states the Master Theorem for T(n) = a*T(n/b) + f(n): if f(n) = O(n^c) with c < log_b(a), then T(n) = Theta(n^(log_b(a))); if f(n) = Theta(n^c log^k(n)) with c = log_b(a), then T(n) = Theta(n^c log^(k+1)(n)); and if f(n) = Omega(n^c) with c > log_b(a), then T(n) = Theta(f(n)). Ren derives the first case by building a recursion tree, summing the work a^i * f(n/b^i) across all i levels down to the base case, and evaluating the resulting geometric series. Applying the theorem to blocked multiplication (a=8, b=2) confirms Theta(n^3); applying it to Strassen's recurrence (a=7, b=2) gives Theta(n^log2(7)), approximately n^2.81, better than cubic (the recitation notes that subsequent research has pushed the exponent lower still, into the 2.3x range).

Finally, Ren revisits the median-of-medians recurrence from Lecture 2, T(n) = T(n/5) + T(7n/10) + Theta(n), which doesn't fit the Master Theorem's form because it has two differently sized recursive terms. He sketches an inductive proof instead: assuming T(n) <= K*n for all sizes smaller than N, substituting into the recurrence shows the bound holds for N as well provided the constant K is chosen large enough, confirming the Theta(n) result asserted in the earlier lecture.

Before you watch

• Watch Lecture 1 (interval scheduling and its weighted DP) and Lecture 2 (convex hull, median finding, and the median-of-medians recurrence) first, since this recitation directly builds on and completes arguments from both.
• Review how to draw and analyze a recursion tree, since it is the main analytical tool used throughout.

Check your understanding

1. Why does sorting requests by start time and asking a binary include/exclude question reduce the number of distinct subproblems compared to trying every request as a possible first pick?
2. What is the recurrence for naive blocked matrix multiplication, and why does it fail to improve on the Theta(n^3) naive algorithm?
3. How does replacing eight sub-multiplications with Strassen's seven change the exponent in the resulting time complexity?
4. State the three cases of the Master Theorem in your own words: what property of f(n) decides which case applies?
5. Why can't the Master Theorem be applied directly to T(n) = T(n/5) + T(7n/10) + Theta(n), and what technique is used instead to show it is Theta(n)?