Solving recurrence relations — In Simple Language

Parts:

1. Building Recurrence Relations in plain readable English
2. Solving recurrence relations — In Simple Language (You are here)

General Idea:

We use Backward Substitution to keep solving the recurrence relations again and again till we reach our base case.

Confused? Its expected. But before we dive into Backward Substitution let’s take a quick recap of building recurrence relations.

Aquick recap of building recurrence relations:

Let’s say we have this simple piece of code that recursively prints all numbers from 1 to n in reverse order.

function printReverse(n) { // If this takes T(n) time to execute
  if(n == 0) return    // This is a constant time operation = 1
   
  console.log(n)       // This is a constant time operation = 1 
  printReverse(n-1)    // This takes T(n-1) time to execute
}

And since, T(n)=summation of all the functions of times required by each line within the function, the recurrence relation formed is:

When n = 0, which is our base case:
    T(n) = 1
When n > 0,
    T(n) = 1 + 1 + T(n-1)
  .:T(n)= T(n-1) + 2
  Since, 2 is a constant, we can asymptotically write:
    T(n) = T(n-1) + 1

in short:

when n = 0, which is our base case:
    T(n) = 1
When n > 0,
    T(n) = T(n-1) + 1

In simple words: When n is more than 1, time taken to print n numbers in reverse is equal to time taken to printn-1 numbers in reverse, plus a constant time operation which is, in this case, printing the number n itself. And when n reaches 0, that is when base case is reached, time taken to for the function t execute is constant, which is 1.

Now how can we calculate time complexity of the algorithm with these recurrence relations?

From the recurrence relations above:

Since T(n) = T(n-1) + 1      ... Let's call this equation 1

then by SUBSTITUTING n-1 in place of n in equation 1, we get:
      T(n-1) = T((n-1)-1)+1
    .:T(n-1) = T(n-2)+1      ... Let's call this equation 2

Now, SUBSTITUTE equation 2 in 1, we get:
      T(n) = [T(n-2) + 1] + 1
    .:T(n) = T(n-2) + 2      ... Let's call this equation 3.

Now what does this mean?

Well, let’s say if T(n) = T(n-1) + 1before first recursion step, then before its second recursion step, T(n) becomes T(n) = T(n-2) + 2. Simple, no?

So how much does T(n) become before third recursion? And before fourth? Before fifth?

And also, how many times does it even have to recurse?
The answer is that it recurses till it reaches its base case of T(0)=1.

But in how many recursion steps will T(n) reach T(0)?

We’ll answer these questions in a while. For now, let’s try to find out what T(n) becomes before its third recursion:

From equation 3, T(n) = T(n-2) + 2
Let's SUBSTITUTE n-1 in place of n in equation 3, we get:
    T(n-1) = T((n-1)-2) + 2      
  .:T(n-1) = T(n-3) + 2      ...Let's call this equation 4

Now, SUBSTITUTE equation 4 in equation 1, we get:
    T(n) = [T(n-3) + 2] + 1
  .:T(n) = T(n-3) + 3        ...Let's call this equation 5

So this says that after its third recursion, T(n) becomes T(n-3)+3.

Before 1st recursion: 
T(n) = T(n-1)+1
Before 2nd recursion:
T(n) = T(n-2)+2
Before 3rd recursion:
T(n) = T(n-3)+3
.
.
.
.
We can easily deduce that before 4th recursion:
T(n) = T(n-4)+4
.
.
.
And before 5th recursion:
T(n) = T(n-5)+5
.
.
.
And so on till we reach out base case...

Let’s assume we reached out base case:

Now let’s say we reach the base case before K th recursion step:

Therefore, we can deduce that:

T(n) = T(n-K)+K               ... Let's call this equation 6

Now, since our base case is:

when n = 0:
    T(n) = 1
In other words, T(0) = 1

we can assume that n, n-1, n-2, n-3, ..., n-(k-2), n-(k-1), n-k has reached 0.

So we can say n — K = 0. Therefore n = K.

If we put n = K in equation 6, we get:

T(n) = T(n-n)+n
.: T(n) = T(0) + n
Since we know, T(0) = 1 from our base case, we can say:
T(n) = 1+n
And asymptotically T(n) = O(n)

Now trust me, this is simple. Just lengthy at start. But go through this once again. I am sure you’ll also feel this is easier than you thought it could be.

Conclusion:

We learnt to analysize time complexity of recursive functions using Backward Substitution.

Todo:

As an exercise, try finding time complexity of the fibonacci function discussed in the previous chapter about building recurrence relations. Good luck! 👍🏾

What’s next?

In the next section, all we will do is build recurrence relations for different types of functions and solve them to find their complexity.

Disclaimer:

This is just an attempt to make you understand solving recurrence relations in simple language. This article, by far, does not even scratch the surface of the topic. I urge you to dig deeper into the topic and learn more.