# 3.3.3. Master Theorem

# Master Theorem 1

• [Neapolitan 2.8]
• Let a, b, and c be nonnegative constants.
• The solution to the recurrence T (1)=1, and T(n)=aT(\frac n c)+bn, for n>1 for n a power of c is
  • 1. T(n)=O(n), if a<c
    2. T(n)=O(n \log n), if a=c
    3. T(n) = O(n \log ca), if a > c
• Prove this by induction!
• Avoid divided-and-conquer if, for example–
  • An instance of size n is divided into two or more instances each almost of size n.
  • An instance of size n is divided into almost n instance of size \frac n c, where c is a constant.
• The divide-and-conquer strategy often leads to efficient algorithms, although not always!

# Master Theorem 2

212p