# 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) + 100T(2) = 3*

**How to solve a recurrence relation running time ?**

**MASTER THEOREM**

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.

Problem: *T(n) = T(2n/3) + 1T(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 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 !

Recurrence Relation Made Easy

41 Students enrolled

★★★★☆ (5 ratings) | Self Paced

*The links are here:*

YouTube: randerson112358

Udemy Course: Recurrence Relation Made Easy

Website: EverythingComputerScience.com