Trusted answers to developer questions

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.

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(\frac{n}{b}) + f(n)$

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

represents the number of subproblems in the recursion, and it must be greater or equal to one (`a`

`a >= 1`

).is assumed to have the same size for each subproblem, and`n/b`

`b`

must be greater than one (`b > 1`

) to ensure a proper divide and conquer recurrence analysis.must be an`f(n)`

*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.

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.

The following are some of the asymptotic bounds of `T(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) < n^{log_b^{a}}$

$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) = n^{log_b^{a}}$

$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) > n^{log_b^{a}}$

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

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

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

Given values:

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

Substituting the values of a and b:

$n^{log_b^{a}} = n^{log_4^{2}} = n^2$

This satisfies case 1:

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

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

Final answer:

$T(n) = \theta(n^2)$

$T(n) = 2T(\frac{n}{2}) + n$

Given values:

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

Substituting the values of a and b:

$n^{log_b^{a}} = n^{log_2^{2}} = n$

This satisfies case 2:

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

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

Final answer:

$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

Related Courses