Session 13: Recurrences, Master Theorem & Divide-and-Conquer

Overview

Phase B begins: one session per week from here. Setting up and solving recurrences, and proving a divide-and-conquer algorithm correct.

Lecturer

Ali Zbeeb (CSE)

Session Information

• Date and Time: Monday 2 November 2026 — 17:30-19:30
• Place: (to be announced)
• Online Meeting Link
• Session Recording

Core Concepts

• Setting up a recurrence from an algorithm
• Solving recurrences by “unrolling” and by recursion trees
• Substitution method: guess, then prove by induction
• Master’s Theorem: statement, the three cases, worked applications, and a case where it does not apply
• Divide and conquer: mergesort, binary search, and Karatsuba
• Worked case study: proving mergesort correct by strong induction, both that the output is sorted and that it is a permutation of the input

Slides

Session 13 Slides: Download PDF

Readings

• CLRS, Ch. 2, 4

Exercises & Extra Steps

• Practice (not collected): solve T(n) = 2T(n/2) + n by unrolling, by recursion tree, and by the Master Theorem
• Practice (not collected): solve T(n) = T(n−1) + n and T(n) = 2T(n/2) + n log n
• Practice (not collected): produce a recurrence the Master Theorem cannot solve and identify which hypothesis fails

Navigation

• ← Previous: S12: Asymptotics — Big-O from the Definition
• Back to Course Overview
• Next: S14: Programming Paradigms & Functional Programming →

Questions? Reach out on the course WhatsApp!