# 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

**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