Master Theorem

Question 1

Describe the Master Theorem formula:

Answer 1

T(n) = aT(n/b) + f(n) Where: a = how many subproblems n/b = size of each subproblem

Question 2

What is the master theorem time complexity for Karatsuba’s algorithm?

Answer 2

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

• n*^{log_b a} = n^{log₂ 3} ≈ n^1.59
• f(n)* = cn
• cn* is O(n^1.59-0.1)

T(n) is θ(n^{log₂ 3})

Question 3

What is the master theorem time complexity for the Merge Sort algorithm?

Answer 3

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

• n*^{log₂ 2} = n
• f(n)* = cn
• cn* is θ(n)

T(n) is θ(n log n)

Question 4

We solve the recurrence of T(n) = aT(n/b) + f(n) by comparing ? with ?

Answer 4

f(n) is compared with n^{log_b a}

Question 5

Master Theorem solutions - Case 1: if f(n) is much smaller than n^{log_b a} then…

Answer 5

f(n) is O(n^{log_b a})
and
T(n) has time complexity n^{log_b a}

if f(n) is O(n^{log_b a-e}) for some e>0, then
T(n) = θ(n^{log_b a})

Question 6

Master Theorem solutions - Case 2: if f(n) is the same as n^{log_b a} then…

Answer 6

f(n) is θ(n^{<em>l</em>og_b a})
and
T(n) has time complexity n^{log_b a} log n

T(n) = θ(n^{log_b a} log n)

Question 7

Master Theorem solutions - Case 3: if f(n) is much bigger than n^{log_b a} then…

Answer 7

f(n) = Ω(n^{log_b a})
and
T(n) has time complexity f(n)

if f(n) is Ω(n^{log_b a+e}) for some e>0,
and the regularity condition holds, then
T(n) = (f(n))

Question 8

What are the three cases when the Master Theorem doesn’t work?

Answer 8

when a < 1
T(n) = 0.5T(n/2) + n

when f(n) is negative
T(n) = 2T(n/2) - log n

When f(n) is smaller but not small enough:

• f(n)* is O(n^{log_b a}) but f(n) is not O(n^log_ba-e) for any e>0
• T(n)* = 2T(n/2) + n/log n