How To Solve Recurrence Relations

Image for post
Image for post

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

Image for post
Image for post
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:

How To Solve A Recurrence Relation Running Time ?

1. Use The 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:

Using the Master Theorem, we must identify our a,b, and d values.

Image for post
Image for post

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)

2. Use The 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

Image for post
Image for post
Recurrence Relation Made Easy


YouTube: randerson112358
Udemy Course: Recurrence Relation Made Easy
Website: EverythingComputerScience.com
Support: https://www.patreon.com/randerson112358

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store