- Master Theorem is the method by
- In Master
- When analyzing algorithms, we only care about the asymptotic behavior.

**The Master Theorem**

The master method depends on the following theorem.

T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive.

### What is Master Theorem?

Let *a ≥ 1* and *b > 1* be constants, let *f(n)* be a function, and let *T(n)* be defined on the non negative integers by the recurrence.*T(n)= aT(n/b)=f(n)*

where we interpret *n/b* to mean either *[n/b]* or *[n/b]*. The *T(n)* can be bounded asymptotically as follows.**if f(n)= O(n ^{logb a-∈}) for some constant ∈ > 0, then T(n) = Θ(n^{logb} a)**

**if f(n)= Θ(n**^{logb a}) then T(n)=Θ(n^{logb}lgn)

**if f(n)= Ω(n**^{logb a+∈}) for some constant ∈ > 0 and if a f(n/b)≤cf(n) for some constant c < 1 and all sufficiently large n, then T(n)= Θ(f(n)).**Generic Form**

The master theorem concerns recurrence relations of the form:

T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive.

*n*is the size of the problem.*a*is the number of sub problems in the recursion.*n/b*is the size of each sub problem. (Assume that all sub problems are essentially the same size.)*f (n)*is the cost of the work done outside the recursive calls, which includes the cost of dividing the- problem and the cost of merging the solutions to the sub problems.

**Case 1**

**Generic form**

If *f(n) = O (n ^{c}) *where

*c < log*(using Big O notation) then:

_{b}a*T (n) = Θ (n*

^{logb}^{a})**Case 2**

**Generic form**

If it is true, for some constant k ≥ 0, that:*f(n) = Θ (n ^{c} log^{k} n)* where c = log

_{b}a

then:

*T(n) = Θ (n*

^{c }log^{k+1}n)**Case 3**

**Generic form**

If it is true that:*f(n) = Ω (n ^{c}) where c > log_{b} a*

and if it is also true that:

*af ( n/b ) ≤ kf(n)*for some constant

*k < 1*and sufficiently large

*n*(often called the regularity condition)

then:

*T (n) = Θ (f(n))*

**Examples:**

LetT (n) = T (n/2) + 1/2 n. What are the parameters? Solution:^{2}+ na=1, b=2, d=2, Since 1 < 2, case 1 applies. Thus we conclude that^{2}T (n) ∈ Θ(n^{d}) = Θ(n^{2})

LetT (n) = 2T (n/4) + √n + 42. What are the parameters? Solution:a = 2, b = 4, d = 1/2Therefore which condition? Since2 = 4, case 2 applies. Thus we conclude that^{1/2}T (n) ∈ Θ(n.^{d}log n) = Θ(√n log n)

T(n) = 9T(n=3)+n. Herea = 9,b = 3,f(n) = n, and n^{logb}a = n^{log}_{3}9 = Θ(n^{2}). Since f(n) = O(n^{log3}^{9−∈}) for∈ = 1, case 1 of the master theorem applies, and the solution isT(n) = Θ(n.^{2})

**When you cannot use master theorem?**

You cannot use the master theorem if*T *(*n*) is not monotone, ex: *T *(*n*) = sin *nf*(

*n*) is not a polynomial, ex:

*T*(

*n*) = 2

*T*(

*n*2 ) + 2

*n*

bcannot be expressed as a constant, ex:

b

*T*(

*n*) =

*T*(

*√n*)