# 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) = 1When 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) = 1When 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 print`n-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 1then 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 2Now, 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) + 1`before 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) + 2Let'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 4Now, 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)+1Before 2nd recursion:T(n) = T(n-2)+2Before 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) = 1In 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) + nSince we know, T(0) = 1 from our base case, we can say:T(n) = 1+nAnd 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.