M3.2 & M3.3: Solving Recurrences

Question 1

What are Recurrences?

Answer 1

A recurrence relation expresses the time complexity of a problem in terms of its subproblems.

Question 2

Substitution Method for solving Recurrences

Answer 2

Make a guess for the solution and prove it by induction.

Question 3

Recurrence Tree Method for solving Recurrences

Answer 3

Expand the recurrence to find a pattern and sum it up.

Question 4

Master Theorem

Answer 4

T(n)=aT(n/b ​)+f(n)

• a≥1.
• b>1.
• f(n) is asymptotically positive.