Master Theorem

Question 1

You use case 1 if:

Answer 1

if n^logb(a) > f(n)

Question 2

You use case 2 if:

Answer 2

if n^logb(a) = f(n)

Question 3

You use case 3 if:

Answer 3

If n^logb(a) < f(n)

Question 4

Case 1 of Master Theorem is:

Answer 4

If f(n) is O(n^logb(a-€), Then T(n) is theta(n^logb(a))

Question 5

Case 2 if Master Theorem is:

Answer 5

If f(n) is theta(n^logb(a) • log^k(n)), then T(n) is theta(n^logb(a) • log^k+1(n))

Question 6

Case 3 of Master Theorem is:

Answer 6

If f(n) is Omega(n^logb(a - €)), then T(n) is theta(f(n))

Question 7

What is epsilon (€) in master theorem (In cases 1 & 3)?

Answer 7

Epsilon is gained by subtracting n^logb(a) and the power of f(n) from whichever is larger. I.e, typically, in case 1, it’ll be n^(logb(a)) - f(n), where in case 3 its the reverse.