Divide and Conquer Master theorem Examples

The Master Theorem provides a straightforward way to determine the time complexity of recurrence relations common in divide-and-conquer algorithms. Specifically, it applies to recurrences of the form: $T(n)=a\times T(\frac{n}{b})+f(n)$ This page provide solutions to problems solving using the master theorem, the details about master theorem is discussed in the Master theorem.

Example 1

Solve the recursion: $T(n)=2T(\frac{n}{2})+n$ Known information:

• $a=2$
• $b=2$
• $f(n)=n$

Compare growth rate, determine which case the expression falls into:

• Non-recursive part: $f(n)=n=\text{Uptheta}(n^1)$
  • $c=1$
• Recursive part: ${\log }_{b}a={\log }_{2}2=1$
  • ${\log }_{b}a=1$

We can confirm $c={\log }_{b}a$, when $f(n)=\text{Upomega}(n^c)$, the example fits case 2. Therefore: $T(n)=\text{Uptheta}(n\log n)$

Example 2

Solve the recursion: $T(n)=3T(\frac{n}{4})+n$ Know information:

• $a=3$
• $b=4$
• $f(n)=n$

Compare the growth rate, determine which case the expression falls into:

• Non-recursive part: $f(n)=n=1$
• Recursive part: ${\log }_{b}a={\log }_{4}3\approx 0.792$

We can confirm that $c>{\log }_{b}a$, when $f(n)=\text{Upomega}(n^c)$, the example fits case 3. Therefore: $T(n)=\text{Uptheta}(n)$

---

Back to parent page: Divide and Conquer

AlgorithmDivide_and_ConquerMaster_Theorem