FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Master Theorem



Master Theorem

How Does the Master Theorem Work?

The Master Theorem solves recurrence relations by comparing two important terms.

  • nlogba
  • f(n)

The relationship between these two terms determines which case of the Master Theorem should be applied. 


             T(n)=aT(n/b)+f(n)

                     │

          Find logb(a)

                     │

      Compare with f(n)

                     │

     ┌────────┼─────────┐

     │        │         │

  Smaller   Equal    Larger

     │        │         │

  Case 1   Case 2   Case 3

Figure 2 : Decision Process of the Master Theorem

Step-by-Step Procedure

  1. Write the recurrence relation in the standard form.
  2. Identify the values of a, b and f(n).
  3. Calculate logb(a).
  4. Find nlogba.
  5. Compare f(n) with nlogba.
  6. Select the correct case.
  7. Write the final Time Complexity.

Case 1 of Master Theorem

Condition

f(n) grows slower than nlogba

f(n)=O(nlogba-ε) where ε > 0

Case 1 in Very Simple Language

Suppose a company has 10 managers, and every manager assigns work to two employees. The amount of work done by the employees is much larger than the time spent assigning the work.

Since the recursive work dominates the dividing and combining work, the total running time mainly depends on the recursive calls.

This situation belongs to Case 1.

Result of Case 1

If f(n) is smaller than n^(logb a) Then T(n)=Θ(n^(logb a))

Solved Example 1

T(n)=8T(n/2)+n Step 1 a=8 b=2 f(n)=n Step 2 log₂8=3 Therefore n^(log₂8)=n³ Step 3 Compare n and n³ Since n is much smaller than n³ Case 1 applies. Answer Θ(n³)

Solved Example 2

T(n)=9T(n/3)+n a=9 b=3 f(n)=n log₃9=2 n^(log₃9)=n² Compare n and n² n is smaller. Therefore Case 1 Final Answer Θ(n²)

Solved Example 3

T(n)=16T(n/4)+n² a=16 b=4 f(n)=n² log₄16=2 n^(log₄16)=n² This example does NOT belong to Case 1. It belongs to Case 2.

Common Mistake

Students often compare only the coefficients (such as 16 and 4) instead of comparing f(n) with nlogba. Always calculate logba first before deciding the case.

Remember

If f(n) is smaller than nlogba, then immediately think of Case 1.

A simple memory trick is:

Smaller → Case 1

Case 2 of Master Theorem

Condition

f(n) grows at the same rate as nlogba

f(n)=Θ(nlogba)

Case 2 in Very Simple Language

Imagine a company where every manager divides the work equally among two employees.

The time required to divide the work and combine the final result is almost equal to the time spent solving the smaller problems.

Neither part dominates the other. Both contribute equally to the total execution time. This situation is called Case 2. 


           Recursive Work

                 ▲

                 │

      -----------------------

      │                     │

Recursive Work      Dividing Work

      │                     │

      -----------------------

                 │

           Both are Equal

Figure 3 : Case 2 - Both parts contribute equally.

Result of Case 2

If f(n) = n^(logba) Then T(n) = Θ(n^(logba) log n)

Solved Example 1

T(n)=2T(n/2)+n a = 2 b = 2 f(n)=n Step 1 log₂2 = 1 Step 2 n^(log₂2) = n¹ = n Step 3 Compare n and n Both are equal. Therefore, Case 2 Answer Θ(n log n)

Solved Example 2

T(n)=4T(n/2)+n² a=4 b=2 f(n)=n² log₂4=2 n^(log₂4)=n² Both are equal. Case 2 applies. Final Answer Θ(n² log n)

Practical Application - Merge Sort

Merge Sort divides an array into two equal halves until each sub-array contains only one element. After that, all the sub-arrays are merged back into a sorted array.

The recurrence relation of Merge Sort is

T(n)=2T(n/2)+n

Here,

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

Since f(n)=n^(log₂2), Merge Sort belongs to Case 2. Therefore,

Time Complexity Θ(n log n)

Practical Application - Binary Search

Binary Search repeatedly divides the search space into two equal parts. Its recurrence relation is

T(n)=T(n/2)+1

Although Binary Search is a Divide and Conquer algorithm, it does not satisfy the equality condition required for Case 2. Therefore, it belongs to a different case of the Master Theorem.

Shortcut Trick

If f(n) and nlogba are exactly equal, then immediately think

CASE 2

Exam Tip

In AKTU examinations, the recurrence T(n)=2T(n/2)+n is one of the most frequently asked questions. Students should remember that its answer is always Θ(n log n).

Remember

Smaller → Case 1

Equal → Case 2

Case 3 of Master Theorem

Condition

f(n) grows faster than nlogba

f(n)=Ω(nlogba+ε) where ε > 0

Case 3 in Very Simple Language

Suppose a company spends very little time solving smaller problems, but a very large amount of time combining the final reports.

In this situation, the combining work dominates the recursive work. Therefore, the total execution time mainly depends on f(n). 


Recursive Work

██████

Combining Work

████████████████████████████

Case 3

Combining Work Dominates

Figure 4 : Case 3 - f(n) dominates the recursive work.

Result of Case 3

If f(n) > n^(logba) Then T(n)=Θ(f(n))

Solved Example 1

T(n)=2T(n/2)+n² a=2 b=2 f(n)=n² log₂2=1 n^(log₂2)=n Compare n² and n n² is larger. Therefore, Case 3 Answer Θ(n²)

Solved Example 2

T(n)=4T(n/2)+n³ a=4 b=2 f(n)=n³ log₂4=2 n^(log₂4)=n² n³ > n² Case 3 Final Answer Θ(n³)

Comparison of All Three Cases

Case Condition Result
Case 1 f(n) is Smaller Θ(nlogba)
Case 2 f(n) is Equal Θ(nlogba log n)
Case 3 f(n) is Larger Θ(f(n))

Decision Flowchart


              Start

                │

      Find log_b(a)

                │

      Compare f(n)

                │

      ┌──────┼──────┐

      │      │      │

 Smaller Equal Larger

      │      │      │

 Case1 Case2 Case3

Figure 5 : Selecting the Correct Case of the Master Theorem.

Memory Trick

Remember This Rule

Smaller → Case 1

Equal → Case 2

Larger → Case 3

Where is the Master Theorem Used?

  • Merge Sort
  • Binary Search
  • Quick Sort (Average Case)
  • Strassen Matrix Multiplication
  • Karatsuba Multiplication
  • Closest Pair of Points
  • Computational Geometry
  • Parallel Algorithms

Limitations of the Master Theorem

  • Applicable only to Divide and Conquer recurrences.
  • The recurrence must follow the form T(n)=aT(n/b)+f(n).
  • Not suitable for T(n)=T(n−1)+1.
  • Cannot solve every recurrence relation.

Common Mistakes

  • Using the wrong values of a and b.
  • Forgetting to calculate logba.
  • Comparing coefficients instead of growth rates.
  • Ignoring the regularity condition for Case 3.

Practice Problems

  1. Solve T(n)=2T(n/2)+1.
  2. Solve T(n)=3T(n/2)+n.
  3. Solve T(n)=4T(n/2)+n².
  4. Solve T(n)=8T(n/2)+n.
  5. Solve T(n)=9T(n/3)+n².
  6. Solve T(n)=2T(n/2)+n².
  7. Solve T(n)=16T(n/4)+n².
  8. Solve T(n)=5T(n/5)+n.

AKTU Important Questions

  1. State the Master Theorem.
  2. Explain all three cases with examples.
  3. Solve T(n)=2T(n/2)+n using the Master Theorem.
  4. Discuss the limitations of the Master Theorem.
  5. Differentiate between Case 1, Case 2 and Case 3.

Interview Questions

  1. What is the Master Theorem?
  2. When can it be applied?
  3. When should it not be applied?
  4. Explain all three cases.
  5. What is the recurrence relation of Merge Sort?
  6. Can Binary Search be solved using the Master Theorem?
  7. Why is Merge Sort classified under Case 2?
  8. What is the regularity condition?

Summary

The Master Theorem is one of the most important techniques for solving recurrence relations in Divide and Conquer algorithms. It classifies recurrence relations into three cases based on the comparison between f(n) and nlogba. By selecting the appropriate case, the time complexity of many recursive algorithms can be determined quickly without expanding the recurrence relation manually.





Leave Comment

Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com