Change Function To Recurrence Relation

https://youtu.be/_B-ESIPEnhc

Usually when analyzing programs, we start with a recursive definition of the program and try to figure out a closed form or function for the recursive definition and then solve it’s time complexity. Here we are doing the opposite, we are starting with the closed form or function and changing it to a recursive definition.

Below we have our problem or function that we want to change into a recursive definition.

f(n) = 2^n + 1

The base case is the terminating case in recursion, that doesn’t use recursion to give an answer. The base case here is when n=0, to get f(0) = 2.

f(0) = 2⁰ + 1
= 1 + 1
= 2

The recursive case is the case when the function defines itself. Here we try to create a recursive case for our function f(n) = 2^n + 1. If f(n) = 2^(n)+1 then f(n+1) = 2^(n+1) + 1.

f(n+1) = 2^(n+1) + 1
= 2 * 2^n + 1
= (2 * 2^n )+ 1
= (2^n + 2^n ) + 1
= 2 ^n + 2^n + 1
= 2 ^n + 2^n + 1 + 0
= 2 ^n + 2^n + 1 + 1–1
= 2 ^n + 1+ 2^n + 1 –1
= (2 ^n + 1)+ (2^n + 1) –1
= f(n) + f(n) — 1

f(n+1) = f(n) + f(n) — 1
f(n+1 -1 ) = f(n)
f(n + 1–1) = f(n-1) + f(n-1) — 1
f(n) = f(n-1) + f(n-1) — 1
f(n) = 2f(n-1) — 1

The recursive definition for f(n) = 2^n + 1 is below.

f(0) = 2
f(n) = 2f(n-1) — 1

This function time complexity is of course O(2^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 )

Image for post
Image for post

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

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