Day #8 - Recurrences

Iterative Substitution: This technique involves substituting the recurrence relation into itself repeatedly to express the solution in terms of its initial conditions.

Master Theorem:

• Let a>0 and b>1 be constants; let f(n) be a driving faction, which is defined and non-negative for all sufficiently large reals

• Define the recurrence T(n) on all positive integers by

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

• Where aT(n/b) means a’T(n/b) + a’’T(n/b) for some constants a’ >= and a"' >= 0, satisfying a = a’ + a’’