Recurrence Relations & Master Theorem

Question 1

What is a recurrence relation?

Answer 1

A recurrence relation is a recursively-defined function
Suppose that the runtime of a program is T(n), then a recurrence relation will express T(n) in terms of its values at other, smaller values of n

Question 2

What is the general pattern for recurrence?

Answer 2

Start from base case, use the recurrence to work out many cases by directly substituting and working upwards in values of n
Inspect results, then look for the pattern and make a hypothesis for the general results
Attempt to prove said hypothesis - using proof by induction
The extract the large n behaviour using big-Oh family

Question 3

What is the Master Theorem’s General Formula?

Answer 3

T(n) = a T(n/b) + f(n)

Question 4

What is case 1 for the Master Theorem?

Answer 4

T(n) is big-Theta(n^log_b(a)) if c < log_b(a)

Question 5

What is case 2 for the Master Theorem?

Answer 5

T(n) is big-Theta(n^c * (log n)^(k+1)) if:
f(n) is big-Theta(n^c * (log n)^k) and c = log_b(a) & k >= 0

Question 6

What is case 3 for the Master Theorem?

Answer 6

T(n) is big-Theta(f(n)) if f(n) is big-Omega with c > log_b(a) & f(n) satisfies the regularity condition:
a f(n/b) <= k(f(n)) for a k < 1