Recurrence Relations[Math Mondays]

This is the basis of Time Complexity.

May 10, 2022

Happy May 9th y’all,

Today is actually a super good day. Not for any particular reason. It’s just a really good day. I’m sure you really got groovy over the Mother’s Day weekend. We are going to keep the party going with this very important concept.

Today we’re going to be discussing the idea behind recurrence relationships. Recurrence relationships are a crucial idea in Computer Science and Discrete Math. Having a functional understanding of how they work will be a game-changer for your coding journeys.

In this post, I will introduce the concept of Recurrence Relationships. I will then tell you how you can get good with this concept, and how much time you should put into it. If you have struggled with calculating the time complexity of your codes, this will be a game-changer. The idea of time and space complexity was actually derived from recurrence relations.

Basic information

For our purposes, recurrence relations are equations where the value of one term is expressed as a function of the value of the terms that came before it. For recurrence relations, we typically need the recursive equations and a few base cases.

A simple example is something like this-

T(n)=T(n-1)+1
T(0)=0

This recurrence relation can be useful in a lot of contexts (like calculating the length of a list). In fact, all O(n) time operations can be expressed as Recurrence relations like the expression given above. That is a bit of cool math, but outside the scope of this post.

Make sure you cover the posts we have already done about recursion. You can search for posts by topic.

Why Do We Care About Recurrence Relations

I sometimes get DMs that ask me how I can compute the time complexities of some very weird functions. The reason is that my AI and Discrete Math professors were both lunatics with a weird fascination for Recurrence Relations. So I got a ton of practice.

Recurrence Relations give you a very solid for analyzing the algorithms/code you write and identifying your computational requirements.

You, however, don’t need to go through what I did, to get the results. Most of my work was for very specific mathematical functions and niche algorithm formulations. A basic exploration of the different kinds of recurrence relations will be enough-

The work you need is two-fold. One is to do some basic recurrence relations of all kinds. You can literally google recurrence relations questions, and you will get a good set to practice. Get to a point where you can solve them in less than 3 minutes.

Once you do that it is time to look at some of the very common functions. Try to analyze their recurrence behavior, and split it. You will be surprised at how easy it becomes to spot patterns. I recommend the following set of algorithms

Sorting, Searching, Reversing, and Length (of) a List. Merging lists is another good one.
List Math. Includes adding values to all values in a list, summing the elements of a list, etc etc.
Factorial, Ackermann, and other classically recursive functions.

For Step 1, This is a quick example of the kind of Recurrence Relations questions commonly asked-

Spend 3 days practicing the questions and you will be set. Once you become proficient with Recurrence Relations, computing the time complexity of functions will be very easy.

If you want a quick summary, use the following slides I’ve created

Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.

Special Request

This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.

There is a simple form in Substack that you can fill up for it. Here it is. Thank you.

https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform

To get your Substack URL, follow the following steps-

Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.

Click on the circled place to get your URL

You will be redirected to your URL. Please put that in to the survey. Appreciate your help.

In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs

If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.

https://forms.gle/XfTXSjnC8W2wR9qT9

Happy Prep. I’ll see you at your dream job.

Bayes Theorem is amazing,

Devansh <3

To make sure you get the most out of Math Mondays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below

Get 20% off for 1 year