Recurrence relation

A recurrence (or recurrence relation) is an equation that describes a function in terms of its value on smaller arguments. There are a few ways of solving recurrences (i.e., finding their asymptotic bounds for $O$, $\Omega$, $\Theta$):

• Master theorem
• Substitution method
• Recursion tree method
• Recurrence expansion
• Akra-Bazzi method