Change Of Variable Recurrence Relation

Solve Recurrence Relation Using Change Of Variable Method

There are many ways to solve a recurrence relation runtime. One way to do this is a method called “change of variable”. Domain transformations can sometimes be used to substitute a function for the argument of the relation and make it easier to solve. The idea is to select a function for S(m), when given T(n).

Let’s look at an example:

Image for post
Image for post

Let’s rewrite the equation by substituting m=log n, and then plug it back in to the recurrence to get the following:

Image for post
Image for post

Now we will create a new function called ‘S’ that takes in a parameter ‘m’ such that S(m) = T(2^m).

Image for post
Image for post

This means that S(m) = 2T( 2^(m/2) ) + m.

Image for post
Image for post

If S(m) = T(2^m) then S(m-1) = T(2^(m-1)) and S(m/2) = T(2^(m/2)), so we can rewrite our function to get the following:

Image for post
Image for post

Now we can use another technique like the Master Theorem to solve for ‘S’. Once we use this technique we easily see that ‘S’ belongs to O(m log m).

This means that our original function ‘T’ belongs to O(log n * log ( log n) ), since we can simply replace ‘m’ with ‘log n’ because m=log n

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also 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. You can check out my YouTube channel of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

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 )

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Resources:
https://classes.soe.ucsc.edu/cmps201/Fall07/handouts/recur.pdf

https://cs.stackexchange.com/questions/3482/changing-variables-in-recurrence-relations

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