Concept Of Recurrence Relations

Introduction to the Concept

g(n) = g(n-1) + 2n – 1
g(0) = 0
  • this defines function f(n) = n^2, and the recurrence relation:
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 0

Solving a Recurrence Relation

  • There are many techniques to solve Recurrence Relations, the main techniques are Iteration Method (also known as expansion or unfolding method) and the Master Theorem method. 
  • In this post we’ll talk about Iteration Method Continue reading