A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence.

For Example, the Worst Case Running Time T(n) of the MERGE SORT Procedures is described by the recurrence.

T (n) = θ (1) if n=1
 2T + θ (n) if n>1

There are four methods for solving Recurrence

Substitution Method

Iteration Method

Recursion Tree Method

Master Method