Solve Recurrence Relation Using Iteration/Substitution Method

Iteration/Substitution Method

The Iteration Method, is also known as the Iterative Method, Backwards Substitution, Substitution Method, and Iterative Substitution. It is a technique or procedure in computational mathematics used to solve a recurrence relation that uses an initial guess to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones.

Let’s take a look at a recurrence relation problem and try to solve it. By solve it, here I mean get it in a “closed form” . A Closed-Form Solution is an equation that solves a given problem in terms of functions and mathematical operations from a given generally-accepted set. For example, an infinite sum would generally not be considered closed-form.

Image for post
Image for post

Let’s start with the recurrence relation, T(n) = 2 * T(n/2) + 2, and try to get it in a closed form. Note that ‘T’ stands for time, and therefore T(n) is a function of time that takes in input of size ‘n’.

T(n) = 2T(n/2) + 2

Now we need to figure out what T(n/2) is. We can do that by taking “n/2” , and putting it into our original function T(n), to get the following:
Note: We are just replacing n with n/2.

T(n/2) = 2T( (n/2) / 2) + 2
= 2T( n/4 ) + 2

So our original equation looks like the following when k= 2
T(n) = 2T(n/2) + 2
= 2( 2T( n/4 ) + 2) + 2
= 4T(n/4) + 4 + 2

That was our second iteration, so this means k=2 .Now we must figure out what T(n/4) is. We can do that by taking “n/4” , and putting it into our original function T(n), to get the following:

T(n/4) = 2T( (n/4) / 2 ) + 2
= 2T(n/8) + 2

So our original equation looks like the following when k=3
T(n) = 4T(n/4) + 4 + 2
= 4(2T(n/8) + 2) + 4 + 2
= 8T(n/8) + 8+ 4 + 2

That was our third iteration, so this means k=3 . Now we must figure out what T(n/8) is. We can do that by taking “n/8” , and putting it into our original function T(n), to get the following:

T(n/8) = 2T( (n/8) / 2 ) + 2
= 2T(n/16) + 2

So our original equation looks like the following when k=4
T(n) = 8T(n/8) + 8+ 4 + 2
=8(2T(n/16) + 2) + 8+ 4 + 2
= 16T(n/16)+16 + 8+ 4 + 2

That was our fourth iteration, so this means k=4 . Now we must figure out what T(n/16) is. We can do that by taking “n/8” , and putting it into our original function T(n), to get the following:

T(n/16) = 2T( (n/16) / 2 ) + 2
= 2T(n/32) + 2

So our original equation looks like the following when k=5
T(n) = 16T(n/16)+16 + 8+ 4 + 2
=16(2T(n/32) + 2)+16 + 8+ 4 + 2
= 32T(n/32)+ 32 +16 + 8+ 4 + 2

Okay let’s stop here and see if we can see a pattern, if not then you should continue this method or process until you do.

When k=1, we had T(n) = 2T(n/2) + 2
When k=2, we had T(n) = 4T(n/4) + 4 + 2
When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2
When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2
When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2

When k=1, we had T(n) = 2T(n/2) + 2
= T(n) = 2T(n/2) + 2 →T(n) = 2T(n/2) + 2(1)

When k=2, we had T(n) = 4T(n/4) + 4 + 2
= T(n) = 4T(n/4) + 4 + 2 → T(n) = 4T(n/4) + 2(2 + 1)

When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2
= T(n) = 8T(n/8) + 8+ 4 + 2 → T(n) = 8T(n/8) + 2( 4 + 2 +1)

When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2
= T(n) = 16T(n/16)+16 + 8+ 4 + 2 → T(n) = 16T(n/16)+2(8+ 4 + 2 +1)

When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2
=T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2
= T(n) = 32T(n/32)+ 2 (16 + 8+ 4 + 2 + 1)

Notice the general form in terms of ‘k’ looks like:
T(n) = 2^k * T(n/ (2^k) + 2 *Summation from i=0 to k-1 of 2^i

The summation from i=0 to k-1 of 2^i is 2^(k) — 1.
So our general form looks like below:

T(n) = 2^k * T(n/ (2^k) )+ 2 *(2^k — 1)
T(n) = 2^k * T(n/ (2^k) )+ 2^(k+1) — 2

When does our recurrence relation stop ? Well it stops when T(n/(2^k)) hits the base case. You may say, but we were never given a base case. That’s okay because every recurrence relation has a base case, and it is always some constant value. So if a base case isn’t provided, we can make one up. So our base case will be T(1) = C, which means when our input is of size 1, the time it takes to execute the function ‘T’ is ‘C’ unit(s) of time, where ‘C’ is some constant unit of time. This means when n = 1, T(n=1) = C.

We must now get our T(n) function from our general form to stop, and therefore need T(n/(2^k))=C, this implies n/(2^k) must equal 1, since T(n/(2^k)=1) = C. Let’s do some algebra below.

= n/(2^k) = 1
= n = (2^k)
= log base 2 of n = k

We now not only have our stopping case, but can also put our value ‘k’ in terms of n, for the entire equation, by plugging in ‘log base 2 of n’ for ‘k’.

T(n) = 2^(log base 2 of n) * T(n/ (2^(log base 2 of n)) )+ 2 *(2^(log base 2 of n) — 1)

T(n) = n * T(n/n) + 2( n — 1)
T(n) = n T(1) + 2n — 2
T(n) = n*(C) + 2n — 2
T(n) = Cn + 2n — 2
T(n) = n ( C+2) — 2

So our guess is that the closed form of our recurrence relation is:
T(n) = n ( C+2) — 2, where C is some constant

NOTE: n ( C+2) — 2 is O(n)

If C = 0 then the equation is
T(n) = n(0 + 2) — 2
T(n) = 2n — 2 = 2( n-1)

Because the closed form is a guess we need to show that our guess is correct and to do that we can use Mathematical Induction.

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, be sure to check it out !

Image for post
Image for post

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

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