# 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:**

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

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

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

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:

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 !

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:

# Computer Science Website:

# Udemy Videos on Algortithm Analysis:

Resources:

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

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