How To Solve Recurrence Relation

What is a recurrence relation ? If you search “Recurrence Relation” on 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.”

A Search on Google for Recurrence Relation

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

How to solve a recurrence relation running time ?


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(n) =
 = 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)

Iteration Method

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”.

Where can you learn more about recurrence relation ?

There are many places to learn more about recurrence relation online, and at school. I have a course on 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 !

Recurrence Relation Made Easy
41 Students enrolled 
 ★★★★☆ (5 ratings) | Self Paced

Recurrence Relation Made Easy

The links are here:
YouTube: randerson112358
Udemy Course: Recurrence Relation Made Easy