How To Solve Recurrence Relations

Image for post
Image for post

Let’s solve the following recurrence relation running time using the iteration / substitution method.

We will use Big Theta as it is the tight bound of a function. We have a function ‘T(n)’, which means it is a function of ‘T’ or time with some arbitrary input size ’n’.

Lets start by rewriting our function and writing the first iteration, we will let ‘k’ represent the number of iterations:

k = 1, T(n) = T(n-1) + log(n), T(0) = 0

k = 2, T(n) = T(n-2) + log(n-1) + log(n)

k = 3, T(n) = T(n-3) + log(n-2) + log(n-1) + log(n)

k= 4, T(n) = T(n-4) + T(n-3) + log(n-2) + log(n-1) + log(n)

General Form:
T(n) = T(n-k) + log(n-(k-1)) + ……+log(n-1) + log(n)
— — = T(n-k) + log(n) + log(n-1) + …..+log(n-(k-1))
— — = T(n-k) + log( n * (n-1) *….. * log(n-(k-1)))

When does this function stop ? The answer is when our function ‘T’ reaches the base case, which is when n=0 such that T(0) = 0. So we want n-k = 0 → n = k. This means where ever we see ‘k’ we can replace it with the variable ’n’, like the following.

T(n) = T(n-n) + log( n * (n-1) *….. * log(n-(n-1)))
— — = T(0) + log( n * (n-1) *….. * log(1)))
— — = 0 + log( n!)
— — = log( n!)

In conclusion we guess that this recurrence relation is Θ(log n!) .

A video on solving the T(n) = T(n-1) + 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 )


YouTube: randerson112358
Udemy Course: Recurrence Relation Made Easy
Website: EverythingComputerScience.com
Support: https://www.patreon.com/randerson112358

RESOURCES

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