How To Solve Recurrence Relation
What is a recurrence relation ? If you search “Recurrence Relation” on Google.com you might get something back like. “ In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.”
Recurrence relation in computer science is just an equation that defines itself.
It has one or more base cases also known as non-recursive output, and a recursive case, input for which a function or algorithm or program calls itself. It can easily describe the run-time or space(memory) needed of a recursive algorithm or program.
Example of Recurrence Relation:
T(n) = T(n/3) + 100
T(2) = 3
To solve a recurrence relation running time you can use many different techniques. One popular technique is to use the Master Theorem also known as the Master Method. “ In the analysis of algorithms, the master theorem provides a solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms.”-Wikipedia
Let’s take the example from the video above and solve it using the Master Theorem.
T(n) = T(2n/3) + 1
T(0) = 0
Using the Master Theorem, we must identify our a,b, and d values.
So let’s rewrite the equation to look like the Master Theorem and then identify those values.
= T(2n/3) + 1
= 1*T(n / (3/2) ) + n⁰, so a=1, b= (3/2) , d=0
So now we just plug in our values to solve the recurrence, if 1 = (3/2)⁰ then the answer is Θ(n^d log n)= Θ(n⁰ log n) = Θ(log n)
Another technique used to solve recurrence relation running time is the iteration method which also goes by many different names. In the iteration method we continue to “unfold” the recurrence until we “see the pattern”.
There are many places to learn more about recurrence relation online, and at school. I have a course on Udemy.com called “Recurrence Relation Made Easy” where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. I also have a YouTube channel of videos where I solve recurrence relations that anyone can check out for free !