Recurrence Relations and Solving using Substitution Method

A recurrence relation 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 satisfies the recurrence. When we analyze recursive algorithms, we express their run...