Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

divide and conquer
master theorem
algorithm

What is the master's theorem?

Abubakkar Arshad

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

The master’s theorem is one of the best and reasonably practical approaches to solve recurrence equations because it directly provides us with the cost of the algorithm. This method applies to the recurrence equations that are in the following form:

T(n)=aT(nb)+f(n)T(n) = aT(\frac{n}{b}) + f(n)

Constraints

The following are some of the constraints of the equation of master’s theorem:

  • a represents the number of subproblems in the recursion, and it must be greater or equal to one (a >= 1).
  • n/b is assumed to have the same size for each subproblem, and b must be greater than one (b > 1) to ensure a proper divide and conquer recurrence analysis.
  • f(n) must be an asymptotically positive function and it is mainly a cost of operations performed other than recursive calls, which includes the cost of dividing the problem and then the cost of merging solutions.

Limitations

We cannot apply the master’s theorem in the following cases:

  • T(n) is not monotone.
  • f(n) is not a polynomial.
  • a is not a constant.

Time complexity comparison

The following are some of the asymptotic bounds of T(n):

T(n)=aT(nb)+f(n)T(n) = aT(\frac{n}{b}) + f(n)

Case 1: If the cost of solving the subproblems increases by a certain factor at each level, then:

f(n)<nlogbaf(n) < n^{log_b^{a}}

T(n)=θ(nlogba)T(n) = \theta(n^{log_b^{a}})

Case 2: If the cost of solving the subproblems is nearly equal at each level, then:

f(n)=nlogbaf(n) = n^{log_b^{a}}

T(n)=θ(nlogbalog n)T(n) = \theta(n^{log_b^{a}} * log \space n)

Case 3: If the cost of solving the subproblems decreases by a certain factor at each level, then:

f(n)>nlogbaf(n) > n^{log_b^{a}}

T(n)=θ(f(n))T(n) = \theta(f(n))

Examples

Let’s jump right into the mathematics of the master’s theorem:


Case 1

T(n)=4T(n2)+nT(n) = 4T(\frac{n}{2}) + n

Given values:

a=4, b=2, f(n)=na = 4, \space b = 2, \space f(n) = n

Substituting the values of a and b:

nlogba=nlog42=n2n^{log_b^{a}} = n^{log_4^{2}} = n^2

This satisfies case 1:

f(n)<nlogbaf(n) < n^{log_b^{a}}

T(n)=θ(nlogba)T(n) = \theta(n^{log_b^{a}})

Final answer:

T(n)=θ(n2)T(n) = \theta(n^2)


Case 2

T(n)=2T(n2)+nT(n) = 2T(\frac{n}{2}) + n

Given values:

a=2, b=2, f(n)=na = 2, \space b = 2, \space f(n) = n

Substituting the values of a and b:

nlogba=nlog22=nn^{log_b^{a}} = n^{log_2^{2}} = n

This satisfies case 2:

f(n)=nlogbaf(n) = n^{log_b^{a}}

T(n)=θ(nlogbalog n)T(n) = \theta(n^{log_b^{a}} * log \space n)

Final answer:

T(n)=θ(n log n)T(n) = \theta(n \space log \space n)

RELATED TAGS

divide and conquer
master theorem
algorithm

CONTRIBUTOR

Abubakkar Arshad
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring